Interview Question for Software Engineer at Amazon.com:

You'd enter the words into a binary search tree, which should be able to search down to a word in log(n) time, with n being the total number of words. If your db doesn't fit on one PC, then you'd place subtrees on different machines and have a master index, indicating which machine had which letter or prefix. For example, if you had 26 machines available, you could put a piece of the tree that corresponds to a letter on each machine. You'd structure the tree so the top node was as close to the middle of the set of possible values on each machine. While this would take some preparation, you'd get fast searches and relatively easy insertions of new nodes.