为什么使用B+Tree

红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

下面先介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器（RAM），如下为简化的主存存取模型：

可以将主存看作是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。

主存的存取过程

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

写主存的过程

系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响。

磁盘存取原理

索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。

读写数据

当需要从磁盘读写数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。当磁头到达目标扇区的第一个位时，驱动器就可以开始读或者写扇区的内容了，这个过程耗费的时间叫做传送时间。

所以，磁盘读写数据时所耗费的时间为：寻道时间 + 旋转时间 + 传送时间。

访问512个字节，磁盘耗费时间主要在寻道和旋转延迟，总耗时大约为SDAM的40 000倍，大约为DRAM的2500倍。

局部性原理与磁盘预读

为了减少磁盘I/O，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。

这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用，因为一般而言程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

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

B-/+Tree索引的性能分析

B-Tree

根据B-Tree的定义，可知检索一次最多需要访问h（h为树的深度）个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。

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

- 每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次I/O。

B-Tree中一次检索最多需要 h-1 次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此 h 非常小，通常不超过3。

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

红黑树

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

B+Tree

上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小：

dmax= floor(pagesize / (keysize + datasize + pointsize))，floor表示向下取整。

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

B+Tree操作

我们将叶节点所在的的页叫做Leaf Page，将非叶节点所在的页叫做Index Page。

插入

B+树的插入必须保证插入后叶子节点中的记录依然排序，同时需要考虑插入到B+树的三种情况，每种情况都可能会导致不同的插入算法，如下表：

Leaf Page满

Index Page满

操作

直接将记录插入到叶子节点

Yes

1）拆分Leaf Page 2）将中间的节点放入到Index Page中 3）小于中间节点的记录放左边 4）大于或等于中间节点的记录放右边

Yes

1）拆分Leaf Page 2）小于中间节点的记录放左边 3）大于或等于中间节点的记录放右边 4）拆分Index Page 5）小于中间节点的记录放左边 6）大于中间节点的记录放右边 7）中间节点放入上一层Index Page

即首先查找需要插入的key在哪个叶节点中，然后将key插入到指定的叶节点中：如果叶节点没有overflow，结束；如果叶节点overflow了，那么就拆分此节点，将节点中间的关键字放到其父节点中，剩余部分拆分为左右子节点；如果拆分出来放到父节点后，父节点也overflow了，那么继续拆分父节点，父节点当做当前，直到当前节点不再overflow。

可以看到，不管怎么变化，B+树总是会保持平衡。但是为了保持平衡对于新插入的键值可能需要做大量的拆分页（split）操作。因为B+树结构主要用于磁盘，页的拆分意味着磁盘的操作，索引应该在可能的情况下尽量减少页拆分的操作，因此，B+树同样提供了类似于平衡二叉树的旋转功能。旋转发生在Leaf Page已经满，但是其的左右兄弟节点没有满的情况下。这时B+树并不会急于去做拆分页的操作，而是将记录移到所在页的兄弟节点上。在通常情况下，左兄弟会被首先检查用来做旋转操作。

删除

B+树使用填充因子（fill factor）来控制树的删除变化。创建索引时，可以指定一个填充因子，以便在索引的每个叶级页上留出额外的间隙和保留一定百分比的空间，供将来表的数据存储容量进行扩充和减少页拆分的可能性。填充因子的值是从0到100的百分比数值，指定在创建索引后对数据页的填充比例。值为100时表示页将填满，所留出的存储空间量最小。只有当不会对数据进行更改时（例如，在只读表中）才会使用此设置。值越小则数据页上的空闲空间越大，这样可以减少在索引增长过程中对数据页进行拆分的需要，但需要更多的存储空间。当表中数据会发生更改时，这种设置更为适当。

填充因子越大，意味着一个索引页包含的索引记录越多，空闲空间越小。一般来说查询的效率越高，因为这样查询的时候，可以减少读取索引页的工作量和减少内存使用。但这样导致的结果是数据变动导致的索引维护的工作量增加，因为索引页的空闲空间小，如果不能在本页内完成索引调整，就会引起调整其他索引页。

所以一般的选择是，数据基本不变化的（例如OLAP的场景，数据只用来分析的），将填充因子设置到足够大,数据经常变化的（例如OLTP的场景），将填充因子设置为足够小。

B+树的删除操作同样必须保证删除后叶子节点中的记录依然排序，同插入一样，B+树的删除操作同样需要考虑以下表的三种情况，与插入不同的是，删除根据填充因子的变化来衡量。

叶子节点小于填充因子

中间节点小于填充因子

操作

直接将记录从叶子节点删除，如果该节点还是Index Paged的节点，用该节点的右节点代替

Yes

合并叶子节点和它的兄弟节点，同时更新Index Page

Yes

1）合并叶子节点和它的兄弟节点 2）更新Index Page 3）合并Index Page和它的兄弟节点