Maintaining search indices with binary trees

Question

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 ?

Answer 1

if I change a single index the whole file will need to be rewritten

So don't change indices. When you add data, remember what words already existed, and store subsequent words afterward. For each word, instead of storing one index in the index file, store several.

There is a lot to optimize on top of that. But I don't think this is a productive use of your time. There are existing programs that can do this (and far more complex use cases, too) very efficiently and without raising a sweat: databases. Use a database engine (Berkeley DB, SQlite, NoSQL, MySQL, TSQL, …).

If you want to understand how to store this kind of data efficiently, read about implementations of database engines. B-trees will be involved at some point.