mysql——索引

1.B/B+树

为了解决mysql在查找过程中，存储多页无法查询的问题，需要使用索引，索引的底层就是使用B/B+树。

发现这篇文章中介绍的B/B+树的相关增删操作写的很详细，借鉴学习一下：

B树和B+树的插入、删除图文详解 - nullzx - 博客园

相同点：

• 一个节点可以存储多个元素。 
• 与B树一样，叶子节点是排序的。
• 每个节点中的元素，也都按照从小到大的顺序排列，即：左小右大。 
• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
• 根节点元素个数： 1<= k <= m-1 (m表示阶数，即：一个节点最多有多少子节点) 非根节点元素个数： m/2 <= k <= m-1

不同点：

• B+树的叶子节点是有指针的，MySQL中采用的是双向指针。
• B+树的非叶子节点的元素是与叶子节点有冗余的。

2.聚簇索引

也叫：主键索引，一级索引

 由上图可以看出：整个结构是一个B+树，不过这里的节点名称不再是B+树中的leaf node而是page node。

最下面一层使用page储存真实的数据，与B+树不同的是page node之间是双向链表；

倒数第二层的目录项其实还是page，不过存储的都是非叶子节点的目录项纪录，只存储一个page中最小的主键以及对应的页码；

当倒数第二层的page超过1条，此时会向上分裂出根节点，分裂出的还是一个page，与倒数第二层相同，存储的是倒数第二层的page node中最小的主键及对应的倒数第二层的page no，再往上依次类推。

储存：最下面一层储存的是实际上的数据，是一个真实存在的page，其大小是16kb，详见本人的另一篇文章mysql——页；假设这16kb中存储了100条数据，倒数第二层中每一个也是一个page，而且其中储存的数据只有主键+page页码，所以能存储更多的数据，假设存储1000条数据，则到第二层就已经能存储1000*100=10w条数据，再往上一层与倒数第二层储存的信息类型一致，所以也是1000，此时就已经10w*1000=1亿条数据，按照mysql官方的建议，一个表中储存的数据量在1000w~2000w之间，超过这个数性能会急剧下降，所以一般来说，B+数的层数不会超过4层。

3.非聚簇索引

也叫二级索引，非主键索引

由上图：

以哪个字段建立索引肯定要对该字段进行排序，这也是建立了索引之后查询快的原因。

与一级索引不同的是，最下面的节点存储的不是所有的信息，而是二级索引的字段以及一级索引的字段，目录项以及根节点与一级索引一致，所以查询的流程是：先找根节点，再找目录项，然后在page中找到对应的一级索引的值，然后根据一级索引的值去一级索引里找对应的记录，这个操作也叫回表。（当然，如果要查询的信息在二级索引的page中，就不会产生回表的操作，不过一般二级索引的page中只会存储索引列及主键列，主要是为了避免空间的浪费）

4.联合索引——多列

 由上图：

page中存储的是建立联合索引的列和主键列，哪个列在前，排序的时候就会先根据哪个列进行排序，所以在查找的时候，如果根据后一个列来查找，name就没办法使用到当前这个联合索引，如果单独使用前一个列查找，那么也可以使用索引，这就是最左匹配原则

5.目录项纪录唯一性

 如果建立二级索引的那一列相同值过多，那么在目录项中，会出现多个记录的记录值相同，如上左图，此时的查询效率也不并不高，为了保证目录项纪录的唯一性，此时会在目录项中添加主键值，提高查询效率。

**************此文章只是本人学习过程中的学习笔记，不做其他用途，如果有其他意见，欢迎一起讨论，谢谢，侵删*************************