深入理解MySQL索引底层数据结构与算法
目录
一 理解索引的特性
二 索引的各种存储结构及其优缺点
在开始讲这一小节之前，我们先来看一下在数据库没有加索引的情况下，SQL中的where字句是如何查找目标记录的。
我们先看下左边表格第二列Col2列的数据时如何查找的，如果我们希望查找where Col2 = 22的记录，我们在没加索引的情况下是按顺序从第一条记录查找，由此可知需要查找5次才能找到；
如果对Col2字段加上索引后，我们假设使用最简单的二叉树作为索引存储方式，再次查找where Col2 = 22的记录这次只需要查找2次就能找到目标记录，效率提高十分明显。
（一） 二叉树
二叉树是一种比顺序结构更加高效地查找目标元素的结构，它可以从第一个父节点开始跟目标元素值比较，如果相等则返回当前节点，如果目标元素值小于当前节点，则移动到左侧子节点进行比较，大于的情况则移动到右侧子节点进行比较，反复进行操作最终移动到目标元素节点位置。
在大部分情况下，我们设计索引时都会在表中提供一个自增整形字段作为建立索引的列，在这种场景下使用二叉树的结构会导致我们的索引总是添加到右侧，在查找记录时跟没加索引的情况是一样的，如下图所示：
（二） 红黑树
红黑树也叫平衡二叉树，它不仅继承了二叉树的优点，而且解决了上面二叉树遇到的自增整形索引的问题，从下面的动态图中可以看出红黑树会走动对结构进行调整，始终保证左子节点数 < 父节点数 < 右子节点数的规则。
在数据量大的时候，深度也很大。从图中可以看出每个父节点只能存在两个子节点，如果我们有很多数据，那么树的深度依然会很大，可能就会超过十几二十层以上，对我们的磁盘寻址不利，依然会花费很多时间查找。
（三） Hash
对数据进行Hash（散列）运算，主流的Hash算法有MD5、SHA256等等，然后将哈希结果作为文件指针可以从索引文件中获得数据的文件指针，再到数据文件中获取到数据，按照这样的设计，我们在查找where Col2 = 22的记录时只需要对22做哈希运算得到该索引所对应那行数据的文件指针，从而在MySQL的数据文件中定位到目标记录，查询效率非常高。
无法解决范围查询（Range）的场景，比如 select count(id) from sus_user where id >10；因此Hash这种索引结构只能针对字段名=目标值的场景使用。
（四） B-Tree
既然红黑树存在缺点，那么我们可以在红黑树的基础上构思一种新的储存结构。解决的思路也很简单，既然觉得树的深度太长，就只需要适当地增加每个树节点能存储的数据个数即可，但是数据个数也必须要设定一个合理的阈值，不然一个节点数据个数过多会产生多余的消耗。
按照这样的思路，我们先来了解下关于B-Tree的一些知识点：
- 度(Degree)-节点的数据存储个数，每个树节点中数据个数大于 15/16*Degree（未验证） 时会自动分裂，调整结构
- 叶节点具有相同的深度，左子树跟右子树的深度一致
- 叶节点的指针为空
- 节点中的数据key从左到右递增排列
在这里需要说明下的是，BTree的结构里每个节点包含了索引值和表记录的信息，我们可以按照Map集合这样理解：key=索引，value=表记录，如下图所示：
BTree的结构可以弥补红黑树的缺点，解决数据量过大时整棵树的深度过长的问题。相同数量的数据只需要更少的层，相同深度的树可以存储更多的数据，查找的效率自然会更高。
从上面得知，在查询单条数据是非常快的。但如果范围查的话，BTree结构每次都要从根节点查询一遍，效率会有所降低，因此在实际应用中采用的是另一种BTree的变种B+Tree（B+树）。
（五） B+Tree（MySQL索引的真正存储结构）
要解答这个疑问需要先了解BTree每个节点结构（上面已经说明）和MySQL数据库它是如何读取索引数据的，索引和表数据在不使用的时候是存储在文件中的，也就是磁盘，当我们执行查询操作时会DBMS（数据库管理系统）首先会先从内存中查找，如果找到直接使用，如果找不到则从磁盘文件中读取；操作系统储存数据的最小单位是页（page），一页假设是4K大小（由操作系统决定），对内存和磁盘读取数据是按一页的整数倍读取的。
这里我们假设数据库一次IO操作就读取1页4K的数据，再假设图中圈起来的元素就是一个大节点，内含多个小节点的索引和数据，其大小是10MB，那么我们要从磁盘中读取完整个大节点需要进行 10M / 4K = 2500次IO操作，这样就可以看出如果大节点数据总量越大，需要执行的IO操作越多，花费的时间也越长，因此为了提高性能，数据库会建议我们一个大节点只存储一页4K大小的数据，这里的数据包含了索引和表记录，另外我们还能计算出树的度Degree应该设置成多大才合理：
Degree = 内存页大小（4K） / 单个索引值字节大小；
进一步分析，索引值的大小相对于整条记录的大小是很小的，如果我们需要查找的数据刚好是在最后，那么前面遍历过的节点中存储的记录数据是不是对我们来说是没用的，它会占用比索引大得多的空间，导致我们一个大节点里能遍历的索引数量大大减少，需要向下继续遍历的几率就更大，花费更多时间查找，那么有没有办法可以优化呢？看下一个问题。
新的B+树结构没有在所有的节点里存储记录数据，而是只在最下层的叶子节点存储，上层的所有非叶子节点只存放索引信息，这样的结构可以让单个节点存放下更多索引值，增大度Degree的值，提高命中目标记录的几率。
这种结构会在上层非叶子节点存储一部分冗余数据，但是这样的缺点都是可以容忍的，因为冗余的都是索引数据，不会对内存造成大的负担。
这点优化有什么用呢？我们直接看下面的B+Tree结构，如果我们进行范围查找where id > 4的记录，我们只需要先找到id = 4的记录后自然就能通过叶子节点间的双向指针方便地查询出大于4的所有记录。
三. 联合索引底层存储结构
单列索引其实也可以看做联合索引，索引列为1的联合索引，从下图就可以看出联合索引的底层存储跟单列索引时类似的，区别在于联合索引是每个树节点中包含多个索引值，在通过索引查找记录时，会先将联合索引中第一个索引列与节点中第一个索引值进行匹配，匹配成功接着匹配第二个索引列和索引值，直到联合索引的所有索引列都匹配完；如果过程中出现某一个索引列与节点相应位置的索引值不匹配的情况，则无需再匹配节点中剩余索引列，前往下一个节点。
感谢大家的阅读，本文如有错误的地方，希望能私信我改正，共同进步！
下一篇文章打算介绍两种常见的数据库存储引擎InnoDB和MyISAM。
