前言
就我个人所知，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效率就变低了。
以上为个人对索引底层原理的一些个人理解。如果有理解的不对的地方，请大家多多指正。互相交流。
后续还会写写MySQL索引失效的问题以及搜索引擎的理解。
网友评论