MySQL索引

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

索引的数据结构：

• 二叉树
• 红黑树
• Hash表
• B-Tree

索引的节点存储的是key(索引列字段)，value(行数据磁盘文件的地址指针)。从索引表中找的时候，都是从根节点去找。（二叉树的数据结构）

二叉查找树：

采取二分查找的思想,O(logN) 的复杂度就可以完成对数据的查找任务，查找所需的最大次数等同于二叉树的高度。

它的特性：

1. 左子树上所有节点的值，小于或等于根节点的值
2. 右子树上节点的值，大于或等于根节点的值

缺点：插入值时，可能会出现"单条腿长"的现象，导致多次插入新节点而不平衡的现象，这时红黑树就出现了。

红黑树：

也叫二叉平衡树。说它平衡的意思就是，它不会变瘸子，左腿或右腿特别长的现象。

它的特性：

1. 节点都是红色或者黑色
2. 根节点都是黑色
3. 每个叶子的节点都是黑色空节点
4. 每个红色节点两个子节点都是黑色的
5. 从任意节点到每个叶子的所有路径都包含相同的黑色节点

红黑树的高度虽然有一定的控制，而数据库当中一般要把索引树的高度控制在3-5层，这点红黑树显然无法做到。

B-Tree：

B-Tree是为磁盘等外存储设备设计的一种平衡查找树，是一种多路平衡搜索树。

不像红黑树只有2个子节点。既然有多个子节点，树的高度就可以控制了，同时它也跟红黑树一样，数据是排序的，可以快速查找；

它的特性：

1. 每个节点最多含有m个孩子
2. 根节点含有[2,m]个孩子
3. 非叶子节点含有[[m/2],m]个孩子节点(向上取整的意思)
4. 所有叶子节点都在同一层

• 每个节点占用一个盘块的磁盘空间，一个节点有两个升序排序的关键字和三个指向子树节点的指针，指针存储是子节点磁盘块地址。

• 两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。

  以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程：

1. 找到根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】

2. 比较关键字29在区间（17,35），找到磁盘块1的指针P2。

3. 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】

4. 比较关键字29在区间（26,30），找到磁盘块3的指针P2。

5. 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】

6. 在磁盘块8中的关键字列表中找到关键字29。

   分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。

B+Tree:

B+Tree是在B-Tree基础上的优化InnoDB存储引擎就是用B+Tree实现其索引结构。

B-Tree的数据结构可以看出，每一个页的存储空间是有限的，如果data数据较大时会导致每个节点存储的key数量很小，但存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，影响查询效率。

在B+Tree树中，所有数据记录点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点只存储key值信息。这样可以增大每个节点key值数量，降低B+Tree的高度。

B+Tree与B-Tree不同：

1. 非叶子节点只存储键值信息
2. 所有叶子节点之间有一个链指针
3. 所有记录值都存放在叶子节点中

• 数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都指向相邻的叶子节点的地址。
• 相比B-Tree来说，进行范围查找时只需要查找两个节点，进行遍历即可，提高了区间访问性能（无需返回上层父节点重复遍历查找减少IO操作）
• B-Tree需要获取所有节点，相比之下B+Tree效率更高。

为什么要使用B+Tree?

一般来说，索引本身也很大，不可能全部存储在内存中，索引往往以索引文件的形式存储的磁盘上。索引查找过程中就要产生磁盘I/O消耗，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。简单说：索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

对比上面的B+树和红黑树，比如查找节点21，红黑树要磁盘IO5次，而B+树只要2次，也就是说磁盘IO次数大致为树的高度，这样B+树就脱颖而出了。

B+Tree的高度一般都在2 ~ 4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

数据库索引采用B+树而不是B树的主要原因: B+树只要遍历叶子节点就可以实现整棵树的遍历，而且在数据库中基于范围的查询是非常频繁的，而B树只能中序遍历所有节点，效率太低。

为什么索引结构默认使用B-Tree，而不是hash，二叉树，红黑树？

hash：虽然可以快速定位，但是没有顺序，IO复杂度高。

二叉树：树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。

红黑树：树的高度随着数据量增加而增加，IO代价高。

如果只选一个数据，那确实是hash更快。但是数据库中经常会选择多条，这时候由于B+树索引有序，并且又有链表相连，它的查询效率比hash就快很多了。

而且数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+树的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。

为什么官方建议使用自增长主键作为索引？

B+Tree的特点，自增主键是连续的，在插入过程中尽量减少页分裂，即使要进行页分裂，也只会分裂很少一部分。并且能减少数据的移动，每次插入都是插入到最后。总之就是减少分裂和移动的频率。