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

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，我们可以发现二者主要在以下三个方面上的不同：

非叶子节点只存储键值信息，不再存储数据。

所有叶子节点之间都有一个链指针，指向下一个叶子节点。

数据都存放在叶子节点中。

看着 B+Tree，像不像是一颗树与一个有序链表的结合体。因而其实 B+Tree 也就是带有树和链表的部分优势。树结构使得有序检索更为简单，I/O 次数更少；有序链表结构使得可以按照键值排序的次序遍历全部记录。
B+Tree 在作为索引结构时能够带来的好处有：
一，I/O 次数更少。这是因为上文也说过，BTree 的节点是存放在内存页中的。那么在相同的内存页大小（一般为4k）的情况下，B+Tree 能够存储更多的键值，那么整体树结构的高度就会更小，需要的 I/O 次数也就越小。
二，数据遍历更为方便。这个优势很明显是由有序链表带来的。通过叶子节点的链接，使得对所有数据的遍历只需要在线性的链表上完成，这就非常适合区间检索和范围查询。
三，查询性能更稳定。这自然是由于只在叶子节点存储数据，所以所有数据的查询都会到达叶子节点，同时叶子节点的高度都相同，因此理论上来说所有数据的查询速度都是一致的。
正是由于 B+Tree 优秀的结构特性，使得常用作索引的实现结构。在 MySQL 中，存储引擎 MyISAM 和 InnoDB 都分别以 B+Tree 实现了响应的索引设计。

文章插图
物理存储
虽说 B+Tree 结构都可以用在 MyISAM 和 InnoDB，但是这二者对索引的在物理存储层次的实现方式却不相同。InnoDB 实现的是聚簇索引，而 MyISAM 实现的却是非聚簇索引。在介绍聚簇索引之前，我们需要先了解以下啥是佩奇，不对，是啥是「主键索引」和「辅助索引」。
其实概念很简单。我们刚刚不是在讲 B+Tree 的时候说过，树的非叶子节点只存储键值。没错就是这个键值，当这个键值是数据表的主键时，那么所建立的就是主键索引；当这个键值是其它字段的时候，就是辅助索引。因而可以得出，主键索引只能有一个，而辅助索引却可以有很多个。
聚簇索引和非聚簇索引的区别也就是根据其对应的主键索引和辅助索引的不同特点而实现的。

聚簇索引说回聚簇索引。先丢个定义。