MySQL数据库索引的底层是怎么实现的

前言

就我个人所知，MySQL目前已经作为绝大数项目的数据库选择。但是经常会需要去处理慢sql导致的各类问题。索引，作为一种常见的处理方式。

思考两个问题：

1.为什么加了索引以后，数据库的查询效率会加快？底层怎么实现的？

2.索引失效的情况有哪些？失效的原因是什么？

简洁描述

索引是快速查找特定列值的行数据的，一种优化查询的数据结构。查找特定列值。例如一条sql里的查询条件是姓名 name = '张三' 。就能查出特定列（姓名列）的特定值（张三）的记录。

另外，它是一种数据结构。那么mysql的数据结构，采用的是B+树。那么，为啥选B+树而不是其他的数据结构。

从数据结构看原理

此处主要讨论下哈希表，平衡二叉树，B树，B+树这4种数据结构，以及为啥选用B+树作为mysql数据库的数据结构。首先看下这四种数据结构示例图。

哈希表

平衡二叉树

B树

B+树

哈希表：哈希表的存储方式是通过计算出一个hash码，然后随机存放到哈希表中。注意：这时候存放的位置，生成的hash值也是无序的。

因此如果采用哈希表的话，根据某个值定向查询速度很快，也就是‘’=‘’的情况。可根据hash值直接找到对应值。但因为hash码是无序的，存储的书序也是无序的，因此hash表数据结构无法完成范围查询，比如>,<，like这些情况。显然是不满足条件的。

平衡二叉树：平衡二叉树是左右子树高度差绝对值不超过1，而且左右子树也都是平衡二叉树。上图中举了1到10在二叉树中的存储方式图的例子。每个节点只能有一个节点。

B树：上图中的B树。B树类似于平衡二叉树，但是图中可看到与二叉树有个很明显的不同：B树的每个节点可以有多个节点。每个子节点之间是不相连的。

B+树：上图中的B+树。B+树和B树的不同可见：B+树的每个叶子节点都是相连的。每个叶子节点包含（左指针|节点值|右指针）。叶子节点会包含所有的节点，非叶子节点的数据会冗余在叶子节点中。

在范围查找上，B树需要回溯节点才能找到目标数据。而B+树由于每个子节点直接都是相连的，因此范围查询的效率，B+树高于B树。

那么不使用平衡二叉树的原因是什么呢？

要解释这个，需要了解磁盘IO。一句话解释就是：磁盘读取数据到内存叫磁盘IO。

如果我们要查找到0010这个值。如果使用平衡二叉树，需要比较4次，也就是需要进行4次磁盘IO。

而B树因为一个节点可以存储多个节点。所以树的高度更低，3次磁盘IO即可。

好的数据结构，应该是能尽量减少磁盘IO的次数。

既然B树和B+树的一个节点可以存储多个节点。这个存储的节点数量是看节点大小和系统配置来计算的。

举例：部署了mysql的操作系统，可以用命令 getconf PAGE_SIZE 来查看每次从磁盘里读取的内存大小是多少。如果查出来是4k，那每个节点存储的节点大小=4k就是最好的，或者4k的倍数。假设每个节点的数据大小是1k，那么B+树上每个节点的节点数就是4或者4的倍数。

B+树只有叶子节点存储数据，非叶子节点不存储数据也是这个原因。如果非叶子节点存了数据，那么每个节点的数据大小变大，B+树节点上能存储的索引key就变少了。树的高度变高，磁盘IO效率就变低了。

以上为个人对索引底层原理的一些个人理解。如果有理解的不对的地方，请大家多多指正。互相交流。

原作者：betterFighter