# Maintaining search indices with binary trees

There are some documents to be indexed, that means I need to read the docs and extract the words and index them by storing at which document they appear and at which position.

For each word initially I am creating a separate file. Consider 2 documents:

• document 1: “The Problem of Programming Communication with”
• document 2: “Programming of Arithmetic Operations”

Here, there are 10 words, 8 unique. So I create 8 files (the, problem, of, programming, communications, with, arithmetic, operations).

In each file, I will store at which document they appear and at what position. The actual structure I am implementing has lot more information but this basic structure will serve the purpose.

file name        file content
the              1 1
problem          1 2
of               1 3 2 2
programming      1 4 2 1
communications   1 5
with             1 6
arithmetic       2 3
operations       2 4


Meaning. the word is located at document 1, position 3 and at document 2, position 2.

After the initial index is done I will concatenate all the files into a single index file and in another file I store the offset where a particular word will be found.

index file: 1 1 1 2 1 3 2 2 1 4 2 1 1 5 1 6 2 3 2 4
offset file: the 1 problem 3 of 5 programming 9 communications 13 with 15 arithmetic 17 operations 19

So if I need the index information for communications, I will go to position 13 of the file and read up to position 15 excluded, in other words the offset of the next word.

This is all fine for static indexing. But if I change a single index the whole file will need to be rewritten. Can I use a binary tree as the index file's structure, so that I can dynamically change the file content and update the offset somehow ?

• I would suggest using a database (unless you have a good reason not to). – Kaveh Apr 20 '12 at 21:15