sim*_*onz 12 b-tree binary-search-tree data-structures
我已经探索了T树和B-/B +树的定义.从网上的论文中我了解到B-tree在分层内存中表现更好,例如磁盘驱动器和缓存内存.
我无法理解的是为什么T树甚至用于平坦记忆？
它们被宣传为AVL树的节省空间的替代品.
在最坏的情况下,T树的所有叶节点只包含一个元素,并且所有内部节点都包含允许的最小量,接近满.这意味着平均只使用分配空间的一半.除非我弄错了,当B树的节点半满时,这与B树的最坏情况相同.
假设两个树都在节点中本地存储密钥,但是使用指针来引用记录,唯一的区别是B树必须存储每个分支的指针.这通常会导致高达50%的开销或更少(超过T树),具体取决于密钥的大小.实际上,这接近于AVL树中预期的开销,假设没有父指针,嵌入在节点中的记录,嵌入在记录中的键.这是阻止我们使用B树的预期效率增益吗？
T树通常在AVL树之上实现.AVL树比B树更平衡.这可以与T树的应用相关联吗？
我可以给你一个个人故事，涵盖了一半的答案，也就是说，为什么我在大约 18 年前编写了一些 Pascal 代码来编程B+ 树。
我的目标系统是一台带有两个磁盘驱动器的 PC，我必须在非易失性存储器上存储索引，并且我想更好地了解我在大学所学的内容。我对商业软件包的性能非常不满意，可能是 DBase III，或者某些 Fox 产品，我不记得了。
无论如何：我需要这些操作：
上一项
索引的最大大小未知
B+ 树让那台慢速的小 PC 真正飞过数据！
叶子有两个额外的指针，因此它们形成了一个双向链表，用于顺序搜索。