MySQL与InnoDB（下）-B＋树与索引

本节主要讲对记录的查找。关于数据库查询，首先要从查询算法的角度优化，从顺序查找、二分查找再到二叉树查找。但每一种算法只能用于特定的数据结构上，比如二分查找必须有序，二叉树查找只能用于二叉查找树上。数据库系统就有着一个使命，它维护着一种特殊的能够满足某种高级查找算法的数据结构，这个数据结构以某种方式指向具体的数据。而我们把这个数据结构就叫做索引。

上一篇讲到存储引擎负责数据的存储和提取。MySQL支持多种存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。

本节主要以InnoDB存储引擎为例来说明。InnoDB 存储引擎在绝大多数情况下使用 B+ 树建立索引，这是关系型数据库中查找最为常用和有效的索引，下面就讲一下为什么B+树索引常用且高效。

说道B+树，就要讨论B树与B+树的异同，而这属于数据结构的范畴，不在本文讨论范围之内。在这里大概讲两句，B树和B+树都属于B类树，为了使用B类树更快找到信息，原则就是在尽量多的在节点上存储相关信息，保证层数尽量少。B类树属于平衡树，每个节点到叶子节点的高度都相同。（更多内容去复习《数据结构》呗）

重点是B+树与B树的不同之处。B树的分支节点与叶子节点都存储数据，而B+树的分支节点存储的是索引，只有叶子节点存储具体的数据。所以对于B+树来讲，扫数据时只需要扫一遍叶子节点即可。下面通过B+树的两种索引方式：聚集索引和非聚集索引来详细说明。

聚集索引

聚集索引就是按照每张表的主键构造一颗B+树，同时叶子结点存放的即为整张表的行纪录数据。举个栗子，一个汉语字典，我们希望查找“张”，我们可以直接翻到字典的最后，找到zh开头，然后找到张。因为字典内容本身是按照拼音排版的，所以字典内容本身就是一个聚集索引。还是有些抽象，那么用下面实例来说明：

如上图，我们在名字字段上建立聚集索引.当需要根据此字段查找特定的记录时，数据库系统会根据特定的系统表查找此索引的根，然后根据指针查找下一个，直到找到。

例如我们要查询“Green”，由于它介于[Bennet,Karsen]，据此我们找到了索引页1007，在该页中“Green”介于[Greane, Hunter]间，据此我们找到叶结点1133（也即数据结点），并最终在此页中找以了目标数据行。 此次查询的IO包括3个索引页的查询（其中最后一次实际上是在数据页中查询）。当然，如果是热点数据（访问频繁），还可能在缓存中查找到。

聚集索引能够让我们在索引的页节点上直接找到数据。此外，由于定义了逻辑顺序，聚集索引能够特别快的访问针对范围的查询。 。比如：如果我们指定一列xxx(或多列)聚集索引，则如果遇到这种语句select* from table where xxx>’2017’ and xxx

非聚集索引

聚集索引中存放着一条行记录的全部信息，而非聚集索引中只包含索引列和一个用于查找对应行记录的『书签』。也就是说，对于非聚集索引，表数据存储顺序与索引顺序无关，叶结点包含索引字段值及指向数据页数据行的逻辑指针。这里也举个栗子：在查找一个不认识的字的时候，我们可以先通过字典的偏旁部首目录，找到字在哪一页，然后通过页码找到“张”。因为字典不是根据偏旁部首排版的，所以需要通过两步才能真正找到。还是有些抽象？如下图：

可以看到，B+树的叶子节点存放的依然是索引，而且还存放着该索引代表的具体数据在那一页。与聚集索引相比：

叶子节点不是数据节点（所以数据不是聚集的）。

叶子节点为每个索引存储一个键-指针映射，可以直接通过该叶子节点找到具体的数据节点页。

我们通过上图发现，叶子节点还保存着一个指针偏移量，通过它可以找到具体的数据行。

其他分支索引节点也与上述存储类似，只不过指向的是下一级的索引节点。

两者的关系

由于实际的数据页只能按照一棵B+树来进行排序，因此每张表只能拥有一个聚集索引。而非聚集索引的存在并不影响数据在聚集索引的组织，因此每张表上可以有多个非聚集索引，非聚集索引页也因此被称作辅助索引。

参考资料：

cnblogs：B树和B+树的总结：

http://www.cnblogs.com/George1994/p/7008732.html

浅入浅出MySQL和InnoDB:

https://draveness.me/mysql-innodb

CSDN;深入理解索引B+树存储:

CNBLOGS:InnoDB索引原理：

https://www.cnblogs.com/George1994/p/7324759.html

oschina：聚集索引与非聚集索引：

https://my.oschina.net/osenlin/blog/287558

CSDN:浅析聚集索引：

《MySQL技术内幕：InnoDB存储引擎》

第五章：索引与算法