特里与B +树

Question

Trie和B +树如何比较按字典顺序排序的字符串[按数十亿的顺序]？它也应该支持范围查询.

来自perf.以及实现复杂性的观点.

Answer 1

我会说这取决于你对Range的意思.

如果你的范围表示为所有单词开头,则a Trie是我说的正确选择.另一方面,Trie不适用于XX和ZZ之间的所有单词之类的请求.

注意,分支因子B+ Tree会影响其性能(中间节点的数量).如果h是树的高度,那么n _max ~~ b ^h.因此h ~~ log(n _max)/ log(b).

随着n = 1 000 000 000和b = 100,我们有h ~~ 5.因此,它意味着只有5个指针解除引用从根到叶.它比缓存更友好Trie.

最后,B+ Tree无可否认比实施起来更难Trie:它更多地Red-Black Tree处于复杂程度.