X-Y Fast Trie in real world applications

Question

I am trying to understand the X and Y Fast Trie data structures and it's not clear why that structures are not used in large database since their asymptotic complexity is less than Log(N). In cases where we have a database of Terabytes, is not better use a Y Fast Trie than for example a B-tree?

Answer 1

There are a few reasons that X-fast or Y-fast tries might not be useful in practice. Here are a few:

1. X-fast tries internally require several linked structures, including a bitwise trie and a doubly-linked list of elements. These don't perform well in database environments where elements are stored on disks and following a pointer can require a disk seek. (For similar reasons, databases often use B-trees over binary search trees). Additionally, they require the use of balanced binary search trees augmented with information to perform a split or join, which adds in extra space and introduces even more pointers to follow.

2. X-fast tries internally require the use of hash tables with worst-case O(1) lookups. Hash tables with these requirements usually require a variety of hash functions to be applied to look up an element and (generally speaking) don't have the best locality compared to, say, a linear-probing hash table, so lookups are a bit slower.

3. Because of the hash tables in X-fast tries and the use of splitting and joining of BSTs in Y-fast tries, these two data structures are only amortized efficient rather than worst-case efficient. In some cases, this is unacceptable - it would be bad if, periodically, a database query ends up taking 100x or 1000x normal time even if on average everything works out quite well.

4. The use of hash tables in X-fast tries and Y-fast tries means that there is an element of randomness involved in the runtimes of the data structures. On expectation they're efficient, but it's possible that due to bad luck, the runtimes of the data structures might be quite high. Specifically, the cost of doing a rehash in an internal hash table or doing a split or join on a tree can be quite high. In a database implementation, reliability is important, so this randomness might hurt.

5. Due to all the reasons outlined above, the constant factors buried in the runtimes of X-fast and Y-fast tries are quite large. In the long run, they should end up being faster than other data structures, but "the long run" might require inputs that are vastly larger than the sorts of data sets that could feasibly fit into a database.

Hope this helps!