inverted index, postings lists, and linked lists

[Edster]

I was reading about the use of inverted indexes and I was trying to build a simple example to better understand how they work (I am most familar with PHP/MySQL). However, I am still unclear what the table structure would look like.

As far as I understand, there is a table called "dictionary " that has a column with each term being indexed (e.g., cat, dog, rat) and another with a reference to a posting list for each term. Fuurther that the posting list points to specific docIDs for each document where the term appears and that it is structured as a linked list (e.g., value/next-pointer chains).

- I assume each term/posting list would be its own table, correct?
- I am very confused about what columns would be in the posting list table. I know docID is one but what else, why? A next-pointer column? why?

I am leaving out term-frequency and position-in-doc stuff to simplify the example.

[Luuk]

After reading a bit about 'inverted indexes' here:

http://en.wikipedia.org/wiki/Inverted_index

That page gives a good example, to understand how it works.

Overy posting has an index attached to it like in the example:

"it":     {(0, 0), (0, 3), (1, 2), (2, 0)}

i Understand the word "it" is stored, and the list "{(0, 0), (0, 3), (1, 2), (2, 0)} " is linked to that word.

So a table could look like this:

CREATE TABLE `NewTable` (
`word`  varchar(20) NOT NULL ,
`docnr`  mediumint NOT NULL ,
`position`  mediumint NOT NULL ,
PRIMARY KEY (`word`, `docnr`, `position`)
)
;

Because for every 'word' you should store in which document it is found ('docnr'), and at what position ('position')

[Luuk]

since you want to know about inverted-indexes, and someone already create a project about it:

http://code.google.com/p/inverted-index/