If your partway searches are from the beginning of the words an index should work fine, because essentially it is a sorted list of words where a binary search can be performed. If a database by seeing "partway search" stupidly refuses to use an index, whether its from the beginning or not, you can always make your own. (index not DB:-) But lets talk about the other possibility: Random starting points. Then your best way is to store your text bzip2-compressed. Because a Burrough-Wheeler-transformed text is its own index for fulltext search. The precise algo is in an old DDJ, but I don't know if it's online by the time you read this. Google for the names of the developers.