深入理解数据库之存储存引擎（二叉搜索树）
B树是数据库存储引擎使用的最多的存储结构之一。许多开源数据库系统也都大量使B用树作为存储结构，多年来已经证明它们能够胜任大多数使用场景。
早在1971年鲁道夫·拜尔(Rudolph Bayer)和爱德华·M·麦克立特(Edward M. McCreight)就提出了B树这种数据结构，并受到广泛的应用。到1979年，B树已经发展出了许多变种形式。
在深入讨论B树之前，让我们首先讨论一下传统搜索树，例如，二叉搜索树、2-3树和AVL树。
二叉搜索树（Binary Search Tree）
二叉搜索树(BST)是一种有序的内存数据结构，用于高效的键值查找。二叉搜索树由多个节点组成。每个树节点由一个键、一个与此键关联的值和两个子指针构成。二叉搜索树从一个称为根节点的节点开始，且一棵树只有一根节点。图2-1展示了一棵二叉搜索树。
在二叉搜索树中搜索空间被每个节点划分成左子树和右子树。如图2-2,一个节点的键值总是大于它左子树所有节点的键值，同时总是小于它右子树所有节点的键值。
从树的根节点沿左子树指针向下到达叶子层(没有子节点的节点)，就可以找到树中包含最小键值的节点。类似地，沿右子树指针向下就可以找到树中包含最大键值的节点。通常，键值可以保存在树中的所有节点中，因此如果从根节点开始搜索，在到达树的最底层之前搜索键就可能被找的。
平衡二叉树
如果随机的插入数据到二叉树中，二叉树就可能处于一种不平衡的状态，即它的一个分支比另一个分支长。图2-3（b）展示了最差的这种情况，这时它更像一个链表。查询的时间复杂度也是和链表一样是线性的，而不像图2-3（a）二叉树具有对数的查询时间复杂度。
上面的例子可能有一些极端，但是它很好的说明了为什么需要对二叉树进行平衡操作。即使不大可能所有的节点都出现在树的某一边，但是树的两边节点还是有很大概率处于不平衡状态，这将对搜索性能产生很大的影响。
如果二叉树的高度为log₂N（其中N是树的节点数目），同时左右子树的高度差不大于1， 这样的二叉树称为平衡二叉树。如果不对二次树做平衡操作，树的形状完全由插入删除操作的顺序决定，二次树在搜索性能上可能就不具有优势。
在平衡二叉树中，每个节点把搜索空间划分为原来的一半，所以时间复杂度是对数的：即O(log₂N)；如果是非平衡二叉树，最差情况下所有节点都在树的某一边，这是时间复杂度就是线性的：即O(N)。
为了避免新节点总是被添加到某一分支上而造成树的不平衡，每次操作后都需要对树进行调整。保证树的高度总最小，每个分支上的节点数目都在允许的范围之内。调整的方法之一就是在添加或删除节点后做一个旋转操作，如果新节点使树处于不平衡状态（两个连续的节点都只有子节点），就以中间节点为旋转轴旋转另外两个节点。如图2-4，以中间节点（3）为转动它的父节点（5）和子节点（2），最终它的父节点成为它的右子节点。
基于磁盘存储的树
前面我们讨论了非平衡二叉树在最坏情况下的查询时间复杂度是O(N),平衡二叉树时间复杂度为O(log₂N)。同时，由于二叉树的较低扇出数（每个节点允许的最大子节点数），平衡二叉树重新调整节点更新指针的频率非常高。因此二叉搜索树并不适合于作为存储在磁盘上的数据结构。
如果存储二叉搜索树在磁盘上，我们会面临下面几个问题。第一个问题就是局部性：因为节点是以随机的顺序添加的，不能保证新添加的节点是临近其父节点的，这就意味着指向子节点的指针有可能指向一个跨越多个磁盘扇区后的位置。当然这个问题可以通过分页二叉树（Paged Binary Trees）的方式在一定程度上缓解；另一个问题是二叉树的扇出数是2，需要执行O(log₂N)次查找才能定位需要查找的节点（即可能需要执行同样次数的磁盘扇区重定位），2-3树和所有低扇出数的树都具有这样的局限性。尽管它们是非常有用的内存数据结构，但是它们并不适合磁盘这样的外部存储的数据结构。
考虑以上这些问题我们可以得出一个结论，如果某种树具有如下特征将更适合磁盘存储：
- 高扇出数：提高相邻键的局部性；
- 低高度：减少磁盘页的重定位次数；
基于磁盘的结构
在前文讨论基于内存和基于磁盘的数据库系统时，我们已经提到了一些数据结构适合于磁盘存储，而有些适合作为内存数据结构。并不是所有的数据结构都适用于磁盘存储的，所以在为数据库系统选择数据结构的时候我们必须考虑存储介质的限制。
如果数据太多太大以至于无法全部保存在内存中时，基于磁盘的数据系统是唯一的选择。这时只能有一部分数据被缓存在内存中，其余数据必须要以一种能够高效访问的方式存储在磁盘上。
普通硬盘（Hard Disk Drives）
大多数传统算法和数据结构是针对使用最广泛的普通硬盘设计的，现在随着新的存储介质不断涌现，适合新存储介质的算法和数据结构（或修改已有算法和数据结构）也不断的出现。
对于普通磁盘，读写时需要旋转磁盘并把读写磁头移动到读写扇区。磁盘旋转和磁头移动都是机械操作，因此读写时定位扇区的开销非常高。但是，一旦定位扇区完成，读写连续扇区的数据成本会低很多。另外需要注意的是对于普通磁盘最小读写单元是一个扇区，典型扇区的大小在512比特到4K之间。
由于定位磁盘扇区的开销非常高，这也是为什么我们经常说磁盘顺序读写的性能要明显的优于磁盘随机读写。
固态硬盘（Solid State Drives）
固态硬盘是用固态电子存储芯片阵列而制成的硬盘。固态硬盘不需要磁盘片旋转，也不需要移动读写磁头到读写扇区，因此随机读写和顺序读写之间的性能并没有太大的不同。但由于迎接和操作系统预读和并行的机制的原因，有时顺序读写和随机读写性能也会有一些不同。图2-5是固态硬盘硬盘的物理组织结构，固态硬盘最小的读写单位是页。
不管是普通硬盘还是固态硬盘，操作系统都抽象成块设备，操作系统屏蔽了磁盘内部结构并对磁盘数据进行缓存。因此即使应用只需要读取一个比特的数据，整个块或也的数据也会一同被读取。在设计适用于磁盘存储的数据结构时，这个因素也需要被考虑。
适合磁盘的数据结构
除了磁盘访问本身的开销之外，设计高效的磁盘存储数据结构的一个主要的限制是最小磁盘读取单位是块。为了追踪某个指针到达特定的位置，我们必须要读取指针所在整个块的数据。虽然有这样一个限制，但是我们可以改变数据结构的布局来克服这一点。
总而言之，设计适合磁盘存储的数据结构时我们必须要考虑目标磁盘的特异之处， 目标是尽量的减少磁盘访问。我们可以通过改进局部性、优化结构内部表示以及减少页外指针的数量来做到这一点。
由此我们可以得出结论：具有高扇出和低高度属性的树才是理想的磁盘存储数据结构，另外平衡时更新指针的数量也需要尽量的少。B树恰好包含了这些思想:增加节点扇出，降低树的高度，减少节点指针数量和平衡操作的频率。下一篇我们会具体讨论B树相关的内容。
分页二叉树（Paged Binary Trees）通过把相邻节点存储到磁盘同一页（如图2-6）来提高数据的局部性。这样只需要在已经读入的当前页中就可以找到指针指向的子节点。但是指针任然可能指向的是一些保存在其它页面的子节点，加载这些页面也会产生一些额外的开销。另外，平衡磁盘存储二叉树时可能会需要调整页面，这时相应节点的指针也需要更新。因此维护磁盘存储二叉树的开销也不可忽略。