Data structure

Maybe you should try a database approach (MSS or Sybase).

Both size and search time can be reduced at the same time. If this would be so all database problems had been solved already. What will be more important for you. The time or the speed.

The tree is always kept balanced, yet there is never a need to perform a balancing operation.  The tree is always more than 50% populated (Except when it starts out empty).  Search operations are faster than a disk based binary tree.  Next and previous operations are close to instantateous.

In this tree make your block size the sector size for the hard disk (or a multiple of that size). (There is no point to reading a smaller block, as the hard disk controller will read the whole sector anyways.)  Then figure out how many keys will fit into this block  (along with the "header" information used to manage the block).  Each block branches by this number of keys, i,e, n times, hence the name n* tree.  This is why it is so good for disk based storage, very few disk reads to get to a key.  You have to do more in memory,  because once a block is read, you need to do a scan for the key to branch on and that might involve scanning through 5 or 10 keys, but that is not the bottleneck, disk I/O is.

Sorry for the delay (the details were coming), but EE is acting slow now.   I forgot to mention that next and previous are so fast, because you buffer the current node so you are doing next and previous in memory.  You only need to go to disk when you go next or previous past the end of the current node.  Also you can read the next or previous node directly.  You do not have to traverse the tree.  Since the tree is kept balanced without using rotates, you can maintain a "linkd list" of nodes at each level.  That is each node contains next and previous offsets to the adjacent nodes on the same level.  This alllows sequential operations to proceed very fast.  The only drawback (and it really isn't one) is the 50% population.  That means up to 50 % wasted space if your key eactly fits your block size.  I don't think that is a problem.

First of all, if you don't have knuth's book, get it.  they (3 volumes) is the bible of algorithms.  I don't remember which volume you need, and mine are in storage, but I beleive it is called "searching and sorting"

In a n* tree there are two types of nodes.  (they are the same format but there is a boolean switch to indicate what type we are talking about.)  The bottom level of the tree has "leaf" nodes and all the levels above (if there are any) are "internal" nodes.  Each nodes begins with a "header" that records if it is a leaf or internal node.  also it has the offsets to the next and prev nodes.  Finally it records the number of keys currently stored in the node.  (That is important, because the node might not be full.)
Following this header is the key info.  This info is the key and the offset to the node associated with the key.  I just store it as an array of key&offsets.  This array must be at least 3 items long of the algorithm fails.  (Your key has to be short enough or your nodes large enough to fit 3.)  You keep these keys sorted inside each node.  

The empty index starts out with just one node, the head node (in the header to the index file you must record the offset of the head node, as it will move.)  The key count is 0.  This is a leaf node. Add keys are added, you place them in the head node and keep it sorted.  When the node is full and you need to add one (any time, not just in this case), you split the node in two.  This involves adding another node, to the immediate right of the current node.  (It is stored at the end of the file, its logical position is to the right.)  The 2nd half of the keys are moved to this node to the right and the first half of the keys remain with the original (left node).  Now there is room to add the new key to one or the other node.  (Some points, when a node splits the new node is allways the same type as the original.  This is also the time when you set the next and previous offsets.) .Now the new node has to be added to the tree.  Thus you go up one level and add its first key to the node above.  If there is room great, if not, you need to split this node and continue up.  If you continue up the tree and reach the head node and need to it and it is full, then you split the head node, and add a new head head node above these two nodes.  thus the index now has a new head.  This process keeps the tree perfectly balanced and uses a minimal number of disk accesses in both adding and searching.

I hope that helps.  If not, get knuth.

Another type of tree that you canuse would be a radix tree.  This would be much smaller (substancially), but it is slower.  The number of disk access is exactly the number of letters in the word to be found.   (This type of tree allows words of differnet lengths to be stored, which is one reason why it is so small. Most trees require you to use a key that is a specific length (the longest word you have, and pad shorter ones with spaces.).  I can give you details on this type of tree too, but it is likely to be slower than the n* tree.

>> I still can't see why extracting a sequence of words should be faster than with a B-tree
I'm not sure what you mean here.

>> Mainly because the base is likely to be located on CD-ROM.
If this information is static, that is, words aren't being added or deleted, that is different.
The N* tree can be filled for this case (well nearly filled as there may no be enough words to exactly fill a node for this case.  This would be a fast way to access the data, but I don't know if I think it would be the best.  n* trees code is quite complex, but definitly worth it because the tree can have endless additions and deletions and still remain balanced with very vew operations.  You don't care about that though, you just need to create the file once and stick it on disk.  You want it to search fast, but it doesn't need to be alteredable.

I think for your case, I would use a slightly "modified" array to store the words.  This will give you close to 100% storage space, and binary access speeds, (slower than N* trees, but your life will be easier and you'll get smaller storage.)  Essentually, this solutiojn will be an array of sorted words, but with some optimisation for disk access.   What I would do is pick a block size, preferably the sector size on a CD.  Your file will consist of an array of these blocks.  Inside each block store as many words that will fit, in sorted order.  Use a NUL character to mark the end of the word and the start of the next word immediately follows.  The only wasted space is the NUL characters and the space at the end of the block that doesn't fit a word.  You can search this file using a binary search.  i.e. You get the middle block of the file.  If the word occurs on it, you are done.   if not look to see if  it occurs in the half before the block or the half after the block, etc...
This may be more disk access than an N* tree--making it slower. But actually since you get far better packing (even when the N* tree  is made full as it could be for your case) this will reduce that effect.  (For small files this method could be faster.  eventually there will be a crtical point at which the n* tree is faster.)

Say you have a 1 million words and average only 10 words per block  (seems small to me, but I want to give you a worst case).  You would be looking at no more than 23 disk accesses to find the word.  Not great, but not too bad.  (any binary algorithm will be the same).  (Now a n* tree with only 5 words per node (small again) can do the search in only 9 access.  And the difference between the two becomes larger as the total number of words increases and the number per node increases.  With 10 words per node a n* tree needs only 6 accesses)

It looks like the choice is between speed and size (as always) with programing convenience thrown in on the size side.

You know what, for your case there is no rule that says that for an n*  tree all nodes have to have the exact same number of keys stored.  You could use an n* algorithm that stores the varible length keys nodes.  (Again you need a NULL or a length to indicate the key length.)  That combined with the fact that you can insert in sorted order allows for close to perfect packing.  That will be fast and will be efficient.  (Now it is larger than the "array" method for several reasons, but probably no more than a factor of 2 at the most.)  I would consider that.

I'm pretty sure an n* tree where the keys are different lengths is going to give you the best results.  The wasted space is pretty minimal (more than others still) but the number of accesses to disk will be very minimal.  When doing a search n log(x) (the nth log of x) where n is the number of branches per node (not constant, but use an average or worse case) and x is the total number of words.  As you can see this is far far better than a binary search where the accesses would be 2 log(x).  By keeping your blocks at the clustor size (and on cluster boundaries) you make accesses fast.  (You can save space by removing the unused space at the end of a block, but that would missalign blocks and would slow things down by about a factor of 2).  Another thing you can do is to organize the tree so that within the file the 1st level nodes (1 node really) is first, then the 2nd level nodes etc.  (I have no idea how to do so, the normal tree is not like that).  This will make the search potentially faster as the read head only has to move in one direction (most likely).  Next an previous are going to be very fast, they invoke at most one access and often none.  Take a look at knuth and the standard implimentation, then let me know if you have questions.  

(one thing knuth doesn't menthion is that to pack the thing, you add the words in order and when  you split a node don't put half the keys in each node.  Put all that fit in the left node (that should be exactly the ones that were in the original node. and put the addition key (should be the one being added) in the right node.  you get 100% packing except the last nodes of each level might not be full if there aren't enough keys.  Now this still consumes extra space because you have multiple levels, but not that much because the levels quickly get small as you move up the tree.).