Vgbhfive's Blog

B-Tree和B+Tree的探秘之旅

Posted on Edited on

B-Tree

结构特征

为了描述B-Tree ，首先定义一条数据记录为一个**二元组[key, data]**，key 为记录的键值，对于不同数据记录，key 是互不相同的，data 为数据记录除key 外的数据。
那么B-Tree 是满足下列条件的数据结构：

  • d 为大于1的一个正整数，称为B-Tree 的度。
  • h 为一个正整数，称为B-Tree 的高度。
  • 每个非叶子节点由n-1 个key 和n 个指针组成，其中d<=n<=2d 。
  • 每个叶子节点最少包含一个key 和两个指针，最多包含2d-1 个key 和2d 个指针，叶节点的指针均为null 。
  • 所有叶节点具有相同的深度，等于树高h 。
  • 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) 。

1.jpg

查找伪代码

在B-Tree 中按key 检索数据的算法非常直观。
首先从根节点进行二分查找，如果找到则返回对应节点的data ，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null 指针，前者查找成功，后者查找失败。

1
2
3
4
5
6
7
8
9
BTree_Search(node, key) {
    if(node == null) return null;
    foreach(node.key) {
        if(node.key[i] == key) return node.data[i];
        if(node.key[i] > key) return BTree_Search(point[i]->node);
    }
    return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

使用

B-Tree 有一系列有趣的性质。例如一个度为d 的B-Tree ，设其索引N个key ，则其树高h 的上限为logd((N+1)/2) ，检索一个key ，其查找节点个数的渐进复杂度为O(logdN)。
从这点可以看出，B-Tree 是一个非常有效率的索引数据结构。
另外，由于插入删除新的数据记录会破坏B-Tree 的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree 性质。

B+Tree

结构特征

B-Tree 有许多变种，其中最常见的是B+Tree ，例如MySQL 就普遍使用B+Tree 实现其索引结构。
与B-Tree 相比，B+Tree 有以下不同点：

  • 每个节点的指针上限为2d 而不是2d+1 。
  • 内节点不存储data ，只存储key，叶子节点不存储指针。

2.jpg

使用

由于并不是所有节点都具有相同的域，因此B+Tree 中叶节点和内节点一般大小不同。
这点与B-Tree 不同，虽然B-Tree 中不同节点存放的key 和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree 往往对每个节点申请同等大小的空间。

带顺序访问指针的B+Tree

结构特征

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。

3.jpg

使用

在B+Tree 的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree 。
做这个优化的目的是为了提高区间访问的性能，例如图中如果要查询key 为从8 到12 的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

扩展

现在大部分的文件系统及数据库系统普遍采用B-/+Tree 作为索引结构，那么我们来简单的说一下索引的理论基础。

主存存取原理

磁盘存取原理

局部性原理和磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。
为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。

这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。
页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k ），主存和磁盘以页为单位交换数据。
当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

索引的性能分析

上文说过一般使用磁盘I/O 次数评价索引结构的优劣。
先从B-Tree 分析，根据B-Tree 的定义，可知检索一次最多需要访问h 个节点。
数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O 就可以完全载入。

为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

  • 每次新建节点时，会直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node 只需一次I/O 。
  • B-Tree 中一次检索最多需要h-1 次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d 是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

综上所述，用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构，h 明显要深的多。
由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

上文还说过，B+Tree 更适合外存索引，原因和内节点出度d 有关。从上面分析可以看到，d 越大索引的性能越好，而出度的上限取决于节点内key 和data 的大小：

1
dmax=floor(pagesize/(keysize+datasize+pointsize))

floor 表示向下取整。由于B+Tree 内节点去掉了data 域，因此可以拥有更大的出度，拥有更好的性能。

参考资料

https://www.kancloud.cn/kancloud/theory-of-mysql-index/41846

个人备注

此博客内容均为作者学习所做笔记，侵删！
若转作其他用途，请注明来源！