MySQL索引资料总结-蒲公英云

MySQL索引资料总结

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

本文是对一些讲解mysql数据库优秀文章的收集

索引类型

索引是在MYSQL的存储引擎层中实现的，而不是在服务层实现的。所以每种存储引擎的索引都不一定完全相同，也不是所有的存储引擎都支持所有的索引类型。MYSQL目前提供了一下4种索引。具体引擎对应索引如下：

link：三种引擎对应的四种索引说明

B-Tree 索引

B-Tree 索引：最常见的索引类型，大部分引擎都支持B树索引。下面文章详细地说明了mysql常用的B-tree索引的原理及其注意事项：

link：B-Tree索引的原理

B树和B+树的数据结构

B-Tree索引使用的是B-tree的数据结构，上面的文章已大概讲解到。具体的数据结构其一些B树的概念在下面文章提及。

B树数据结构详解

看完之后需要需要注意的是，B树的高度计算里面讲述错误。如下：

若B树某一非叶子节点包含N个关键字，则此非叶子节点含有N+1个孩子结点，（这里是错误的，N是指代一共有N个关键字，而N+1是最下面的叶子节点的最大数量，我这里的叶子节点指的是最下面那层节点的指针指向的那些空结点）
如下：

我们可以得出：
因为根至少有两个孩子，因此第2层至少有两个结点。
除根和叶子外，其它结点至少有┌m/2┐个孩子，
因此在第3层至少有2*┌m/2┐个结点，
在第4层至少有2*(┌m/2┐^2)个结点，
在第 I 层至少有2*(┌m/2┐^(l-2) )个结点
考虑最后的叶子结点层第L层，因为整棵树一共有N个关键字，所以叶子结点层的结点个数最多为N+1，为什么是N+1呢？N个关键字排成一列可以有N+1个孩子结点，如果整颗树的孩子结点都是满的，即所有的孩子结点的指针都有指向下一个孩子。那么最后一层最后便是最多的N+1个结点。如果非叶子节点里面的指向孩子结点的指针没有满，即一些指向空结点，那么最后一层的孩子结点便会小于N+1。
所以2*(┌m/2┐^(L-2)）≤N+1，也就是L层的结点最多为N+1个，即： L≤ log┌m/2┐((N+1)/2 )+2；
所以
当B树包含N个关键字时，B树的最大高度为L-1（因为计算B树高度时，我们最后一层实际的结点指向的空节点作为叶子结点，所以叶结点所在层不计算在内，应该减掉），即：L - 1 = log┌m/2┐((N+1)/2 )+1。
这才是正确的计算B树高度的方式。