深入浅出MySql索引

深入浅出MySql索引 索引的作用

提高数据查询效率

索引的常见模型

可以用于提高读写效率的数据结构很多，这里三种常见、也比较简单的数据结构，它们分别是哈希表、有序数组和搜索树

哈希表

键 - 值(key - value) 的形式，哈希思路：把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。
哈希冲突的处理办法：链表

哈希表适用场景： 只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。

有序数组

按顺序存储。查询用二分法就可以快速查询，时间复杂度是：O(log(N))
有序数组在等值查询和范围查询场景中的性能就都非常优秀。

场景：有序数组索引只适用于静态存储引擎，

二叉搜索树

二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。

InnoDB 的索引模型

每一个索引在 InnoDB 里面对应一棵 B+ 树，即一个主键索引树和多个非主键索引树。
执行查询的效率，使用主键索引 > 使用非主键索引 > 不使用索引。
如果不使用索引进行查询，则从主索引 B+ 树的叶子节点进行遍历。
主键索引和普通索引的查询有什么区别？
非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护(所以推荐自增主键)

中间插入记录：需要逻辑上挪动后面的数据，空出位置
数据页满了： 根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去（页分裂,原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%）

当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

主键选择：主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小，从性能和存储空间方面考量，自增主键往往是更合理的选择。

业务字段做主键：不回表，典型的 KV 场景。

回表

回到主键索引树搜索的过程，称为回表

覆盖索引

如果值已经在 某个索引树上了，因此可以直接提供查询结果，不需要回表。由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

最左前缀原则

B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。

不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

在建立联合索引的时候，如何安排索引内的字段顺序？

评估标准是，索引的复用能力。因为可以支持最左前缀，所以当已经有了 (a,b) 这个联合索引后，一般就不需要单独在 a 上建立索引了。

1. 如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。
2. 考虑原则就是空间。比如上面这个市民表的情况，name 字段是比 age 字段大的 ，可以创建一个（name,age) 的联合索引和一个 (age) 的单字段索引。

索引下推

在 MySQL 5.6 之前，只能一个一个回表，到主键索引上找出数据行，再对比字段值。
而 MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。


直接判断age，只需要回表 2 次。

常见的树结构 二叉树

二叉树是一种二分查找树，有很好的查找性能，相当于二分查找。
但是当N比较大的时候，树的深度比较高。数据查询的时间主要依赖于磁盘IO的次数，二叉树深度越大，查找的次数越多，性能越差。

多叉树

多叉树就是节点可以是M个，能有效地减少高度，高度变小后，节点变少I/O自然少，性能比二叉树好

B树

B树简单地说就是多叉树，每个叶子会存储数据，和指向下一个节点的指针。

B+树

B+树是B树的改进，简单地说是：只有叶子节点才存数据，非叶子节点是存储的指针；所有叶子节点构成一个有序链表

优点：

1. 对于在内部节点的数据，可直接得到，不必根据叶子节点来定位。
2. 非叶子节点不会带上指向记录的指针，这样，一个块中可以容纳更多的索引项，一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。
3. 叶子节点之间通过指针来连接，范围扫描将十分简单，而对于B树来说，则需要在叶子节点和内部节点不停的往返移动。具体的来讲，如何想扫描一次所有数据，对于b+树来说，可以从因为他们的叶子结点是连在一起的，所以可以横向的遍历过去。而对于b-树来说，就这能中序遍历。
4. 磁盘读写代价更低
5. 查询效率更加稳定
   非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

红黑树

红黑树的规则：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

现在想想，理解是平衡树（AVL）更平衡，结构上更加直观，时间效能针对读取而言更高，但是维护起来比较麻烦（插入和删除之后，都需要rebalance）。但是红黑树通过它规则的设定，确保了插入和删除的最坏的时间复杂度是O(log N) 。

设计红黑树的目的，就是解决平衡树的维护起来比较麻烦的问题，红黑树，读取略逊于AVL，维护强于AVL，每次插入和删除的平均旋转次数应该是远小于平衡树。

红黑树 和 b+树的用途有什么区别？

1. 红黑树多用在内部排序，即全放在内存中的
2. B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构。