B树与B+树

从二叉搜索树说起

其实上一篇文章已经对BST进行过讨论,并对AVL,红黑树这样的自平衡二叉查找树分别解决了什么问题进行了讨论。

BST

上面这些数据结构理论上能达到$O(log_2N)$的平均时间复杂度。

这个时间复杂度是基于对内存的操作而计算出来的。倘若我们的数据量十分庞大,内存无法容纳,我们不得不存储在硬盘中。这个时候二叉搜索树还能达到预期的速度吗?

在回答这个问题之前先让我们看看磁盘的存储原理。

磁盘的存储原理

我们知道传统的机械硬盘(不考虑SSD)的磁盘通过电磁性来保存数据的,磁头在高速旋转的磁盘上扫描寻道来读取或改变特定位置的磁性,从而实现数据的读写。

硬盘

上图中间的那个原型磁盘被分为被分成若干个扇形区域,这个区域被称为“扇区(sector)”,硬盘中每个扇区大小固定位512个字节

扇区

为了降低磁头来回寻道的时间,通常我们建议程序员在执行IO操作时,使用连续顺序读写而不是随机读写

理解顺序IO与随机IO:https://flashdba.com/2013/04/15/understanding-io-random-vs-sequential/

二叉搜索树的磁盘IO

树这种数据结构每个节点空间一般都是临时分配的,也就是说每个节点存储的物理位置都是随机的

BST磁盘IO问题

那么每次访问一个节点都可能造成一次随机的磁盘IO

当树的深度越大,随机的磁盘IO次数越多,这将会严重降低二叉搜索树的效率。

为了降低树的深度,B树被发明出来了。

B树

B树也是一种自平衡的树状数据结构,它通常用作文件系统、数据库的索引结构。

B树是Rudolf Bayer和Ed McCreight在1971年发明的,但他们并没有解释字母B所代表的的含义。B可能代表平衡(balanced)、浓密(bushy),也可能是他的名字Bayer或者他们所在的波音(Boeing)实验室。

因为国外的文献中把B树写做”B-tree“,国内的翻译直接翻译成”B-树”,有人可能会误认为它们是两种数据结构(万恶的翻译),但实际上它们指的都是同一种数据结构。

B树中的每个节点可以有两个以上的子节点,每个节点最多可以有m个孩子,其中m被称为B树的阶(order)

每个节点最多可以存储m-1个用于比较的数据(key)

为了保持B树的平衡,B树还有以下几个特性:

1.根结点至少有两个子节点。

2.每个中间节点(根节点和叶子节点除外)都包含k-1个元素和k个孩子节点,其中$\frac{m}{2} <= k <= m$

3.每一个叶子节点都包含k-1个元素,其中$\frac{m}{2} <= k <= m$

2-3Tree

当m等于3的时候,每个节点可以有两个或三个子节点,所以也被叫做2-3Tree

2-3Tree是John Hopcroft在1970发明的。B树实际上就是对2-3Tree的泛化。

下图就是2-3Tree的存储结构。

2-3Tree

插入数据时,当节点中的数据达到3个,就会发生分裂:中间的值将会升级成父节点,比中间值小的将会成为左子节点,比中间值大的将会成为右子节点。

2-3Tree插入操作

同样的当m等于4的时候,就有2-3-4Tree

高阶B树

当m越来越大的时候,B树就成了一个“又胖又矮”的小胖子了。这棵矮胖的树每个节点都存储了很多数据,每次取其中一个节点并使用二分查找,就能立马知道下一个节点的位置了,节点数量以及树的层数的降低使得I/O次数随之降低。

高阶B树

那是不是B树的阶数越高越好呢?

B树的节点是一个数据块,因为节点块子节点数k满足$\frac{m}{2} <= k <= m$,所以最坏的情况会浪费块内一半的空间,阶数m越大意味着空间浪费也越大。这个需要应用程序在空间和时间上进行权衡,一般将块大小设计成磁盘块的大小(磁盘最小存储单位是扇区,磁盘一个扇区512字节,新型磁盘一个扇区有4K)。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 定义key的类型,根据具体需要比较的类型定义 */
# define KEY ...
/* 定义value的类型,根据具体要存储的数据定义 */
# define VALUE ...
/* M为阶数,M大于等于3*/
# define M 10

typedef struct {
KEY key[M-1];
VALUE value[M-1];
/*指向子节点的指针*/
BTNode* BTptr[M];
} BTNode;

关于B树的阶数该如何选择可以参考https://stackoverflow.com/questions/28677734/how-to-decide-order-of-b-tree

B树的变体B+树

通常B树的节点中同时存储了Key和Value,更准确的说应该是Value的引用(存储数据的物理地址)

我们比较的时候只需要Key而已,但是却把Value也取了出来,从而造成了不必要的I/O,虽然只是取出了value的引用,但是当数据库数据量越来越大的时候,对性能的影响也会随之累积而变得十分可观。

另外,B树进行范围查询时需要回溯,对于硬盘中的数据结构而言,一次回溯意味着一次随机IO。

回溯

为了解决这些问题,B+树被发明出来了。

B+树中有几个小规则:

内部的非叶子节点只存储Key,用来索引,不保存Value数据

所有的Value数据都保存在叶子节点中

叶子节点之间用指针串联起来

B+树

当然它的分裂方式也有所不同:中间值在分裂的时候不仅会成为父节点,还会在叶子节点中保留一份。

B+树的分裂

B+树还有另外几个好处:

  • 所有的查找最终都会到叶子节点,从而保证了查询性能的稳定
  • 所有叶子节点形成有序链表,便于范围查询
  • 内部节点只存储key,节点会更小,意味着内存中可以缓存更多的节点

由于B+树的这些优秀特性,各大数据库的索引都是基于B+实现的。比如MySQLOracle等。

参考链接:

https://www.cs.cornell.edu/courses/cs3110/2012sp/recitations/rec25-B-trees/rec25.html

http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html

https://cstack.github.io/db_tutorial/parts/part7.html