05 January 2015

B-tree简介

B-tree是一种树形的数据结构,类似于二叉搜索树,但每个节点可以有多于2个的子节点。因此,二叉搜索树的性质B-tree也都有,但B-tree在磁盘数据访问上有更多地优势。我们知道,CPU访问内存的速度远比磁盘快,然而内存的容量有限,很多时候要操作的数据在内存中无法一次性全部装载,因此需要辅助存储器,然而使用辅助存储器导致的问题是寻找数据的时间远超过处理数据的时间。那么如何在辅助存储器中快速定位需要的数据?B-tree正是为这种需求而设计,它由Rudolf Bayer and Ed McCreight 于1971年发明,(B-tree中的“B”字具体指什么已经没有记载了),可以以树的高度(磁盘seek)和内部节点key的个数(磁盘rotate)作为调整参数来缩短定位时间。

B-tree定义

什么样的树是B-tree?定义一个节点[key,data],key记录键值,不同的记录key值必须不同,data记录除key以外的数据,d为预先设定的任意一个大于1的正整数,定义为树的度(指向子节点的指针数量),h为数的高度,那么B-tree应该满足如下的约束条件:

  • 节点中的key按照非递减的顺序排好序。
  • key和指针互相间隔,节点两端是指针,每个指针要么为null,要么指向另外一个节点。
  • 所有叶节点具有相同的深度,等于树的高度。
  • 如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于v(key1),其中v(key1)为node的第一个key的值。
  • 如果某个指针在节点node最右边且不为null,则其指向节点的所有key大于v(keym),其中v(keym)为node的最后一个key的值。
  • 如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null,则其指向节点的所有key小于v(keyi+1)且大于v(keyi)。
  • 非叶子节点key的数量n-1,指针数量为n,那么n与树的度d满足约束:d<=n<=2d。
  • 叶子节点最少包含一个key和两个指针,最多包含2d-1个key和2d个指针,叶节点的指针均为null 。

下图为一个符合要求的B-tree,它的度为2:

b-tree

树的度大小取决于磁盘块的大小。

B-tree算法

查找

从根节点开始,递归向下搜索:

  • 如果是非叶子节点,若节点key中包含所查找的数值,则返回此节点,否则遍历该节点所有的key,找到 第一个 key比所查找数值大的key 前面那个key,递归查找此key的孩子节点。
  • 如果是叶子节点,没有找到所查找数值,返回NULL。

插入

插入操作在叶节点进行,找到要插入的那个叶节点,进行如下操作:

  • 如果此节点包含key的个数n与树的度数d满足n<2d,则直接在此节点中插入新元素
  • 否则,此节点包含key的个数已经“满了”,对该节点进行如下操作:
    • 1、选取改节点的中间元素(包含新插入元素)。
    • 2、新建两个节点,key小于中间元素的插入左节点,key大于中间元素的插入右节点。
    • 3、中间元素插入父节点,若父节点又满了,重复步骤2。若父节点已是根节点,则创建一个新的根节点。

删除

删除的节点key有两种情况,内部节点key和叶子节点key。分成两个部分,删除和调整

删除:

若是叶子节点key:

  • 直接删除
  • 若删除之后此叶子节点key数量小于d,则调整此叶子节点以满足B-tree约束。

若是内部节点key:

  • 从叶子节点中查找一个此节点的替代,通常是此节点左孩子中最有的叶子节点,或者右孩子中最左的叶子节点。
  • 找到之后替换此内部节点key,并删除叶子节点中这个key。
  • 从叶子节点中删除掉此替换的key之后,若子节点key数量小于d,则调整此叶子节点以满足B-tree约束。

调整,假设删除key后的叶子节点为坏节点,则进行如下之一操作:

  • 1、若坏节点有左兄弟节点且左兄弟节点key数量大于d,则把左兄弟节点最右边的key替换掉父节点key,并把父节点key插入坏节点。
  • 2、否则若坏节点有右兄弟且右兄弟节点key数量大于d,则把右兄弟节点最左边的key替换掉父节点key,并把父节点key插入坏节点。
  • 否则删除父节点key并把此key加入到左孩子节点,然后将右孩子节点合并至左孩子,删除右孩子节点。若删除父节点后,若父节点key数量小于d,则重复1、2、3

参考

1、D Comer, Ubiquitous B-tree; ACM Computing Surveys (CSUR), 1979

2、B-tree

3、MySQL索引背后的数据结构及算法原理