深入理解mysql索引

数据结构展示：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

为什么要使用索引

下面以二叉树为例

如果有一条sql select * from t where t.col2 = 89。那么没有索引的话会进行全盘扫描，需要找到89这条数据需要6次。每一次数据库与磁盘的交互叫做IO，那么需要6次IO。
如果使用二叉树作为索引，如上图，二叉树的特点就是左边的数据根节点小，右边的数据比根节点大。这样找89，先找根节点34，然后89比34大，在34后边继续找。以此类推。找到89只需要2次IO

常用索引的数据结构

常用的索引数据结构有：二叉树、红黑树、hash表、b-tree、b+tree等。

二叉树

上面有讲过，二叉树的特点就是左边的数比根节点的小，右边的数比根节点的大。但是为什么mysql没用二叉树作为索引。根据上图像col1的数据，如果放到二叉树得到的数据结构是这样的

这样查找数据效率也不高。

红黑树

还是根据col1的数据插入到红黑树中，得到的数据结构

也是按1到7的顺序插入，但是红黑树会自动做一次平衡。这样会比二叉树查询效率会高一些。红黑树其实也是二叉树。
但是mysql没有用红黑树作为索引。为什么？红黑树的查询效率和树的高度有关，在数据量小的情况下查询效率自然不错。但是在数据量大的情况下，五六百万的数据，红黑树的高度可想而知。树的高度直接影响了查找的效率。

hash表

hash的数据结构

每次存入数据就会对key进行一次hash，计算出存储的位置。例如存放Alice，先进行hash计算出存放位置，图中存放在2这个位置，用于hash会出现hash碰撞，对于不同的值可能计算出的结果是一样的。
查找数据的时候先对key进行hash计算出所在位置，如果所在位置有多个，在进行key的比较。很多时候hash会比b+tree的效率高，因为key值hash后就能找到对应的位置。mysql是可以选择hash作为索引的

那么hash有什么缺点呢：会发生hash冲突，不支持范围查询，仅能满足‘=’，‘In’查询。

b-tree

有上面红黑树可知，树的高度影响着查询效率，那么如果把树的高度固定或者是其在一定的范围内，是不是就可以保证查询效率。那么b-tree可以做到这一点。先来看看b-tree的数据结构

key表示主键，data为非主键数据，对于不同的数据key是不相同的。图中根节点空白处表示指针 指向存储的是子节点所在磁盘的地址。每个节点中的key从左往右递增排序。节点和key相互间隔。节点两端是指针。指针要么是null，要么存储另一个节点的地址
b-tree的特点：

1. 叶节点具有相同的深度，叶节点的指针为空
2. 所有索引元素不重复
3. 节点中的数据索引从左到右递增排列

从1到10插入到b-tree

4的左右两端分别指向2和6、8所在的节点。2的左右两端指向1和3所在的节点。mysql也没有使用b-tree作为索引

b+tree

想看下b+tree的数据结构，从1到10插入到b+tree中

b+tree把所有的data数据都放在叶子节点中，根节点和子节点key存储的data数据是叶子节点的地址。每个子节点的两端同样指向下一个子节点。同时叶子节点多了指针指向下一个节点。
但是mysql底层索引也没有用这个b+tree，而是优化过的b+tree

mysql的b+tree的数据结构

特点：

• 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接，提高区间访问的性能
• 每个节点都是按照递增顺序排序，并且满足二叉树的左小右大的特点
• 每个叶子节点的两端也保存相邻叶子节点的地址，就是说可以通过20，很快找到18所在的数据，这就是双向箭头的作用

如何查找数据：
先从根节点开始查找，把根节点的数据放入到内存当中，然后采用类似二分法的方式查找。这算一次IO，但是因为在内存当中这次IO是非常快，真正耗费时间的是从根节点定位打子节点，再从子节点定位到叶子节点。
例如查找56，可以直接在根节点找到，那么根节点的56所存储是叶子节点56所在的位置，就会定位的叶子节点56的位置，就可以找到数据。 例如查找20，在根节点中找不到，那么根节点15和56之间的空白处就是存储了子节点的地址，就会访问子节点继续按照这个模式查找。

我们知道树的高度影响着查询效率，那么b+tree能解决这个问题吗？
在mysql中根节点或者子节点称为数据页，每个数据页大约16k，通过SHOW GLOBAL STATUS LIKE 'Innodb_page_size';

根据b+tree的结构图，假设主键key用bigint，bigint在mysql中占8个字节，空白处为子节点的磁盘地址，大约占6个字节。那么每个数据页大约能放1170个元素（一个key+一个指针），叶子节点特殊一些，叶子节点因为包含数据，就算它一条数据1kb，那么能存储16个元素(mysql存储的数据)。所以一个b+tree能存储1170*1170*16大约两千万左右的数据。也就是说千万级别的数据放在高度为3的树中，也就是说查找只需要3次IO。
为什么mysql使用b+tree而不是b-tree
b-tree根节点、子节点、和叶子节点有存储了数据。极大的占用了空间，按照上面b+tree的算法，b-tree每个数据页只能存放16个元素，那么如果存放千万级别数据，需要的高度大于3

mysql索引

索引是帮助mysql高效获取数据的排好序的数据结构

聚集索引

聚集索引不是一个索引的名称，而是一种索引的概念。mysql索引采用b+tree，这个b+tree的叶子节点如果包含了key所对应的整条数据，那么这个索引树就叫聚集索引。只有主键索引是聚集索引。

非聚集索引

b+tree的叶子节点的只包含了部分数据，例如主键，那么这就是非聚集索引。例如除了主键索引外，其他的辅助索引，叶子节点的数据包含的是主键，然后根据这个主键进行回表，根据聚集索引获取到对应的数据。

为什么建议建表的时候必须建主键，并且建议使用整型的自增主键

为什么要建主键：在innodb存储引擎中，表的数据必须要由b+tree来维护，并且这个b+tree的叶子节点包含了对应key的整条数据，就是上面提到的聚集索引。因为只有是主键才会维护这个聚集索引，如果不创建主键的话，mysql会自动选择表中一列数据全部不相同的列作为主键，如果找不到就会创建一列隐藏列作为主键。这样会增加mysql的负担。本身这些工作也不是mysql应该做的。
为什么使用整形主键：整形相对于字符串来说比较大小的效率会高，因为在b+tree中不管是叶子节点还是根节点、子节点都是排好序的，同时整形存储需要的空间比字符串需要的空间要小。
为什么要使用自增主键：在b+tree中都是需要排好序的，如果选择自增，那么插入的时候只需要往后面插入数据就好。如果不是自增，那么数据插入后索引会进行维护，自动排好序，并且有可能做一次平衡。什么是平衡，比如说将子节点的某个key，作为一个冗余key，复制一个放入到根节点中。因此这些步骤增加了mysql的负担。