HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How do XFast and Y Fast Tries compare to B trees in performance?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
fastxfasttriestreesperformancehowandcompare

Problem

I learned that Y fast tries support amortized loglog(u) time insertions , deletions. and loglog(u) time membership, successor and predecessor operations with O(n) space. So when n is closer to U in dense big data environments Y fast tries seem better than B trees.

But most database systems use Btrees internally. I was wondering whats the reason behind it. Does Xfast tries and Y fast tries have a high constant factor? I think the implementation is complex as Xfast tries require threaded tries (with strings as bits of integers in u) and a doubly linked list. And Y fast tries require Xfast tries to store maximum elements of each Balanced Binary Search tree used internally, and also merging and splitting of these Balanced BSTS. Is the complexity of implementation the reason behind them not being used as widely as B trees. Can someone give an intuition on why B trees are preferred against X fast tries and Y fast tries?

Solution

Apart from their more complex structure, Y-fast and X-fast trie assumes that data to be stored are integers, while balanced BSTs only assumes that data be from some ordered universe, not necessarily integers.

Also the Y-fast trie uses balanced BST as a secondary structure.

In addition to the points I highlighted, I believe you will be interested in this similar question about the use of Y-fast and X-fast trie in real-world application. The accepted answer for this question along with the other answer have more detailed discussion.

Context

StackExchange Computer Science Q#157735, answer score: 4

Revisions (0)

No revisions yet.