CSDN|别再一知半解啦，索引其实就这么回事！( 四 )

事实上一颗 BTree 需要满足以下几个条件：
每个叶子结点的高度都是一样的；
每个非叶子结点由 n-1 个 key 和 n 个指针 point 组成，其中 d<=n<=2d, key 和 point 相互间隔，结点两端一定是 key；
叶子结点指针都为 null；
非叶子结点的key都是 [key, data] 二元组，其中 key 表示作为索引的键， data 为键值所在行的数据；
一颗常见的BTree树见下图。

这是一颗三阶的BTree ，可通过键值的大小排序进行数据的查询和检索，其中叶子节点的指针都为空，因此省略没画。从上图可以发现， BTree 的树形状相较于我们之前常见的二叉树等结构，更为扁平和矮胖。
之所以这样设计，还是跟磁盘读取的特点有关。我们知道在建立索引时，也是需要占据物理空间的。而实际上当数据量比较大的时候，索引文件的大小也十分吓人。考虑到一个表上可能有多个索引、组合索引、数据行占用更小等情况，索引文件的大小可能达到物理盘中数据的1/10 ，甚至可达到1/3 。
这就意味着索引无法全部装入内存之中。当通过索引对数据进行访问时，不可避免的需要对磁盘进行读写访问。同时我们还知道，内存的读写速度是磁盘的几个数量级。因此在对索引结构进行设计时要尽可能的减少对磁盘的读写次数，也就是所谓的磁盘 I/O 次数。
这也就是索引会采用 BTree 这种扁平树结构的原因，树的层数越少，磁盘I/O的次数自然就越少。不仅如此，我们上面提到过磁盘预读的局部性原理。根据这个原理再加上页表机制，能够在进行磁盘读取的时候更大化的提升性能。
BTree 相较于其它的二叉树结构，对磁盘的 I/O 次数已经非常少了。但是在实际的数据库应用中仍有些问题无法解决。
一是无法定位到数据行。通过 BTree 可以根据主键的排序定位出主键的位置，但是由于数据表的记录有多个字段，仅仅定位到主键是不够，还需要定位到数据行。虽然这个问题可以通过在 BTree 的节点中存储数据行或者增加定位的字段，但是这种方式会使得 BTree 的深度大幅度提高，从而也导致 I/O 次数的提高。
二是无法处理范围查询。在实际的应用中，数据库范围查询的频率非常高，而 BTree 只能定位到一个索引位置。虽然可以通过先后查询范围的左右界获得，但是这样的操作实际上无法很好的利用磁盘预读的局部性原理，先后查询可能会造成通过预读取的物理地址离散，使得 I/O 的效率并不高。
三是当数据量一大时， BTree的高度依旧会变得很高，搜索效率还是会大幅度的下降。
问题总是推动改进的前提。基于以上的问题考虑，就出现了对 BTree 的优化版本，也就是 B+Tree 。
B+Tree索引B+Tree 一看就是在 BTree 的基础上做了改进，那么到底改变了什么呢。废话不多说，先上图。

上图实际上是一种带有顺序索引的 B+Tree ，与最基本的 B+Tree 的区别就在于叶子节点是否通过指针相连。一般数据库中常用的结构都是这种带有顺序索引的 B+Tree 。后文探讨的也都是带顺序索引的 B+Tree 结构。
对比 BTree 和 B+Tree ，我们可以发现二者主要在以下三个方面上的不同：