Ultra-fast "Begins With" Query from Disk

I have a 40MB (too big for memory in this case) list of strings that I want to do "begins with" queries on to extract matches. Anyone know of a good data structure for this? Bonus points for an existing os java implementation. I would be willing to sacrifice "begins with" to just exact matching if somethin开发者_如何学Gog already exists. A disk-based trie sounds ideal.

It looks like you need something like this: http://en.wikipedia.org/wiki/Trie

An implementation in Java can be found here, although it isn't disk-based. I'll keep searching :/

Useful papers: Trie methods for text and spatial data on secondary storage, B-tries for disk-based string management

Edit: I came across this might might be useful: MG4J: Managing Gigabytes for Java™

Can't suggest any existing library, but I dealt with similar problem before. It's quite easy, if you don't plan on modifying your list dynamically and you can sort strings in the file (for binary search).

Let's break your 40Mb into 1000 chunks of approximately equal size and keep first string from each chunk in memory. That would be an array of 1000 strings. They're ordered, because original list is ordered.
When you need to execute a query, you can use binary search on that array. This will show you in which chunk result string lies. Then you can read that chunk from disk (approx 40kb) and search in its contents.

E.g., if array holds values ["andrew", "brian", "donald", "john"] and you search for prefix "cris", you know that all Cristophers and Cristians are in the second chunk.