Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms)

[skaller <skaller@users.sourceforge.net>]

On Thu, 2005-11-17 at 00:42 +0100, Oliver Bandel wrote:

> So, say we have 10^6 texts that we want ot have an index for,
> to retrieve the text according to some parts of the text
> (keywords, substrings,...).
> We want to make an index from these texts.

BTree or modern equivalent may be an option.

NTFS directories are BTrees.

Balanced BTree guarantees extremely small constant time lookup
for all keys. (typically 3 or 4 accesses) 
Many updates are also fast constant time. However
the Btrees are very expensive to rebalance, and occasionally
an update requires a global rebalancing which brings the
world to a complete stop for a very long time.

BTree is ideal for large data structures, since the nodes
are chosen to match up with disk block sizes, and the underlying
I/O is done with low level I/O calls, that is, BTree is excellent
for hierarchical storage media (such as virtual memory).

One system I worked on used BTrees with spill list for
those updates which would require a rebalancing.
The merge/rebalancing is then done whilst the tree
is offline, accesses are slowed down by the spill
list until the rebalancing is done.

Btree is probably good for a search engine where you 
run two trees on two servers and do the rebalancing
on the offline one (then swap servers).

Some modern variants amortise the costs differently,
typically reducing the worst case at the expense
of the other operations. In particular, the very
worst way to populate a BTree from a list is if
the list is already sorted, however a smart algorithm
can build an empty skeleton first and populate it
in linear time (provided only you know
how many keys there are). Obviously, the tree
has to be offline until this operation is completed.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net