1 定义

B-tree是一种多路搜索树的结构,是对二叉树的扩展。B通常表示Balance的意思,顾名思义,B-tree也是类似平衡的结构。B-tree通常用来作为数据库的索引。

B-tree具有以下性质:

M 表示顺序(order,1路叶子节点的数量,如下图中是5),M-1为搜索keys数目。

  • 数据内容保存在叶子节点中
  • 非叶子节点存储最多M-1个key用来搜索,key i 表示子树中最小的key + 1
  • 所有的非叶子节点(除root外)具有M/2到M个子节点
  • 所有的叶子节点都具有L/2到L个的数据项目,(对于一些L可能会更短)

如上图所示,是一个order=5的4-ary(路)搜索B-树。如果需要找到12这个值的索引,我们只需从根节点比较大小 41,找到第一个子节点,再找到8-18这两个节点之间,再通过8依次向下比较12,命中索引。

2 实现