Browse thread
[1/2 OT] Indexing (and mergeable Index-algorithms)
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2005-11-17 (08:15) |
From: | skaller <skaller@u...> |
Subject: | Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms) |
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