0%

B-树

在创建索引时,通常采用的数据结构有:Hash、二叉搜索树、红黑树、B树以及B+树。

一、概念

      鲁道夫·拜尔(Rudolf Bayer)和艾华·M·麦克雷(Ed M. McCreight)于1972年在波音研究实验室(Boeing Research Labs)工作时发明了B树,但是他们没有解释B代表什么意义(如果有的话)。道格拉斯·科默尔(Douglas Comer)解释说: 两位作者从来都没解释过B树的原始意义。正如我们所见,“balanced”,“broad”或“bushy”可能适合,其他人建议字母“B”代表Boeing。

      在计算机科学中,B树(英语:B-tree)是一种自平衡的树,能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。