什么是索引
索引是一种利用某种规则的数据结构与实际数据的关系加快数据查找的功能；索引数据节点中有着实际文件的位置，因为索引是根据特定的规则和算法构建的,在查找的时候遵循索引的规则可以快速查找到对应数据的节点，从而达到快速查找数据的效果；其实宏观来说索引其实是一种概念而不是具体的某项技术，只是我们在某个技术中运用得比较广泛和鲜明（比如说数据库）渐渐的有了特定领域的标签，其实在生活中索引的使用无处不在，比如说：书本里的目录；读书时的座位号，考试编号都有类似索引的功能;
总结来所有通过某规则数据结构和实际目标关联，根据特定规则算法快速寻址的功能都可以称之为索引；
二、为什么要用索引
首先我们看下在没有索引的情况下是怎么查找数据的：
我们用一个例子来解释比较直观
（1）没有索引的情况下访问数据：
（2）使用平衡二叉树结构作为索引的情况下访问数据：
第一张图没有使用索引我们会进行顺序查找，依照数据顺序逐个进行匹配，进行了5次寻址才查询出所需数据，第二张图用了一个简单的平衡二叉树索引之后我们只用了3次，这还是数据量小的情况下，数据量大了效果更明显，所以总结来说创建索引就是为了加快数据查找速度；
三、Innodb 的索引选择
Mysql 的默认存储引擎innodb使用B+树作为索引的存储结构，为了让我们能更深入理解B+树，所以我们会对B+树的衍生过程做一些了解。
1、数组和链表的选择
作为最基础的数据存储结构数组和链表，是选用数组还是选择链表来作为索引存储的基本结构呢？首先我们需要从索引和两种数据结构的特性来分析。
数组的特性： 查找快、但是插入、修改数据慢。
链表的特性： 查找慢、插入、修改快。
在数据库的业务场景里插入、修改、查询都是比较频繁的操作，选链表还是数组好像都不完美。既然都不完美，那么我们只能退而求其次，看谁比较容易去完善。从完善的角度来看，那么我们就会从数组里发现一个致命的问题，数组的修改和移动都会导致数组大量的元素迁移，而且在迁移的过程中是不能查找数据的，数组元素迁移没有完成查询出来的数据就可能是错的，这样就导致数组在频繁插入和修改的过程中不仅仅是修改和插入本身慢，而且因为这个而导致查询也用不了，显然这个问题对于修改和插入频繁的数据库来说是无法忍受的。所以我们只能把链表作为索引的基础结构了，那么剩下的就是如何解决链表查询小笼包慢的问题了。
2、从链表到二叉树
如果使用链表来存储数据，那么必须要解决的一个问题就是要解决链表的查询效率问题，我们必须通过一种算法来解决链表查找数据慢的问题，而这里这里就用到了二分查找法，利用二分法思维把链表拆成N个对半分的节点，然后形成了一个数据结构叫二叉查找树，使用了二分法思维衍生出来的树大大提升了查找的性能。
3、从二叉查树到平衡二叉树
二叉查找树极大的提升了链表查找数据的效率，不过我们又发现了一个问题，就是二叉查找树的“高度”不可控，一旦树的节点插入变成向下图一样的结构。
如果树的节点不可控编程变成线性结构，那么就会极大的降低我们的查询效率，所以我们就又需要一种算法来保证二叉树节点的平衡，让树的节点高度差不会太大，这个时候就衍生了一些平衡算法，最终我们的二叉树就有像AVL树和红黑树这些新产品，我们也称这些新产品为平衡二叉树，，平衡二叉树通常会保证树的左右两边的节点层级相差不会大于2。
4、从平衡二叉树到B树
平衡二叉树的出现好像很接近于我们的理想状态了，但好像还有什么优化的空间，我们通过上面两个树的演化过程发现，影响这棵树的查询效率的决定性因素就是树的高度，只要树的层级越少，那么树的查询效率就越高，本着这个原则我们就思考每个节点能不能多存点 数据，只要每个数节点的数据保存的越多，那么我们树的层级就会越少，
B树相对平衡二叉树最大的一个改变，就是B树的每个节点可存储的关键字增多了，特别是在B树应用到数据库中的时候，节点存储关键字的数量充分利用了磁盘块IO的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来），B树只要把节点大小限制在磁盘快大小范围，这样就可以只需要一次IO就读取到节点所有数据，节点存储了更多的关键字，但是并不会影响IO的次数。B树树相对于之前节点可以存储更多的关键字，所以树的层级会比原来少很多，树的层级减少了，那么检索的效率就会大大提升。
5、从B树到B+树
其实B树已经接近我们的理想预期了，但是还是能从B树的上面找到可以优化的地方，比如以下几个方面：
1、B树的节点同时保存了索引的key和数据值（如果节点只保存索引key不保存值，那么是不是会把索引树的层层级更进一步的减少）。
2、因为每个节点保存了数据值，这样的话查询不同的数据效率就会显得不稳定，有些在树的第一层匹配成功就返回，有些则可能需要匹配到树的最后一层才返回。
3、如果要查询所有数据，那么就必须遍历整个B树的每个节点。
B+树在B树的基础上 又做了一些优化，B+树主要做了下面几点的优化。
1、B+跟B树不同，B+树的非叶子节点不保存实际的数据，只保存索引key，所有的数据都会保存到叶子节点。
树层级变少：如果非叶子节点不保存实际的数据值，而只保存索引key，那么相对于B树来说B+树的每个非叶子节点存储的索引key会更多，所以树的层级也会更少，那么查询效率也会更快。
查询更稳定：因为B+所有数据值都是存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定；
遍历整个树更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
2、B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
排序和范围查询更方便：B+树所有的叶子节点数据构成了一个有序链表，这样在进行数据排序和询范围大小查询数据的时候更方便，数据紧密性也更高。
（百度百科算法结构示意图）
总结来说，从平衡二叉树、B树、B+树，总体来看它们的贯彻的思想是相同的，在链表的基础上，如何采用二分法和数据平衡策略来提升查找数据的速度。不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的，在这个基础上，B+树的查找速度快、性能稳定、排序快、扫表快等诸多特点也就让Mysql选择了B+树来作为索引的存储结构。
四、补充
为什么说Mysql的索引树一般都在1-3层的结构？
经常听到别人说Mysql的索引树一般会在3层，这个是有什么依据？ 其实这个的确是有数据计算支撑的，我们可以根据B+树的原理进行一下数据推算，因为磁盘每页数据为4K，而Mysql的B+树对此又进行了一次调整，在Mysql也有自己的页概念，Mysql里的每一页数据等于磁盘4个页的大小，所以在Mysql里面的一页数据其实是16K，那么也就意味着Mysql里B+树的非叶子节点可存储16K的数据。
然后我们按照一个索引大小，如果字段类型为varchar，长度为10，字符类型为utf8mb4，在不考虑其他因素的影响下，一个索引的大小等于 10 _3+2=32字节，我们按照每个非叶子节点的16K来计算，Mysql索引树每个节点能容纳(16_1024)/32=512个索引key。
**索引树的第一层：**第一层是树的根节点，所以索引树的第一层保存索引Key的数量为512个；
**索引树的第二层：**B+树根节点可保存512个索引key，也就是当前B+树有512个分叉，那么第二层索引树节点个数为512个，保存索引Key的数量=512*512=262144。
**索引树的第三层：**第二层key数量为262144，那么第三层的树节点数量也就是262144，那么第三层索引树节点个数为512个，保存索引Key的数量=262144*512=134217728。
根据一个计算我们可以基本得出，类型varchar，长度为10，字符类型为utf8mb4的索引字段，数据在512条之内树结构只有一层。数据在262144之内树只有两层，数据在134217728之内，索引树都会保持在3层之内，而我们的表数据一般而言都保持在千万级以内，所以说Mysql的索引树一般都在1-3层。
20220407-Mysql索引原理
本文转自 https://zhuanlan.zhihu.com/p/213772042，如有侵权，请联系删除。
