一、简介
MySQL官方对于索引的定义为：索引是帮助MySQL高效获取数据的数据结构。即：索引是数据结构。
我们知道，数据库查询是数据库最主要的功能之一，我们都希望查询数据的速度尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。
最基本的查询算法当然是顺序查找
，当然这种时间复杂度为O(n)的算法在数据量很大时显然是糟糕的，于是
有了二分查找、二叉树查找等，
查询的时间复杂度为
O
(nlog2
N
)
。但是二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树，但是数据本身的组织结构不可能完全满足各种数据结构。所以，在数据之外，数据库系统还维护者满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。目前大部分数据库系统及文件系统都采用
B-Tree和B+Tree作为索引结构
。而我们的索引列表是B类树的数据结构，
查询的时间复杂度为
O
(log2
N
)
，定位到特定值得行就会非常快，所以其查询速度就会非常快。
二、为什么要用B+Tree做Mysql索引的底层实现？
二分查找
O
(nlog2
N
)：
要求被检索数据有序。
二叉树
O
(nlog2
N
)
：树的高度太高，寻址时间太长。
平横二叉树：高度会自动平衡，当时高度依然很高，因为一个结点只能存储一个数据。
多路平衡二叉树之B树：一个结点存多个数据，所以树的高度能得到很好的控制，比较好的解决了等值查询，但对于范围查询差
B树的变种B+树：它把数据存到叶子结点一份，节点之间排好序，并且有指向这些元素记录的指针，空间换时间的设计思想。
三、B+树 原理以及 B+树与B树的对比
原理：通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。
图解B+树与查找过程：下面是一颗B+树：
B-树中的卫星数据（Satellite Information）：
B+树中的卫星数据（Satellite Information）：
需要补充的是，在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。
第一次磁盘IO：
第二次磁盘IO：
第三次磁盘IO：
B-树的范围查找过程
自顶向下，查找到范围的下限（3）：
中序遍历到元素6：
中序遍历到元素8：
中序遍历到元素9：
中序遍历到元素11，遍历结束：
B+树的范围查找过程
自顶向下，查找到范围的下限（3）：
通过链表指针，遍历到元素6, 8：
通过链表指针，遍历到元素9, 11，遍历结束：
B+树的特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
B+树的优势：
1.单一节点存储更多的元素，使得查询的IO次数更少。
2.所有查询都要查找到叶子节点，查询性能稳定。
3.所有叶子节点形成有序链表，便于范围查询。
三、分析
通过上面的分析，我们知道
IO次数取决于b+数的高度h
，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小；而m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。
为什么说
B+-tree
比B 树更适合实际应用中操作系统的文件索引和数据库索引？
1) B+-tree的磁盘读写代价更低
B+-tree
的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而
B+
树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比
B+
树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
2) B+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
读者点评
fanyy1991（csdn用户名）道：个人觉得这两个原因都不是主要原因。数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
上述那个问题转载自：
从B树、B+树、B*树谈到R 树
那么在任何时候都应该加索引么？这里有几个反例：1、如果每次都需要取到所有表记录，无论如何都必须进行全表扫描了，那么是否加索引也没有意义了。2、对非唯一的字段，例如“性别”这种大量重复值的字段，增加索引也没有什么意义。3、对于记录比较少的表，增加索引不会带来速度的优化反而浪费了存储空间，因为索引是需要存储空间的，而且有个致命缺点是对于update/insert/delete的每次执行，字段的索引都必须重新计算更新。
那么在什么时候适合加上索引呢？我们看一个Mysql手册中举的例子，这里有一条sql语句：
SELECT c.companyID, c.companyName FROM Companies c, User u WHERE c.companyID = u.fk_companyID AND c.numEmployees >= 0 AND c.companyName LIKE ‘%i%’ AND u.groupID IN (SELECT g.groupID FROM Groups g WHERE g.groupLabel = ‘Executive’)
这条语句涉及3个表的联接，并且包括了许多搜索条件比如大小比较，Like匹配等。在没有索引的情况下Mysql需要执行的扫描行数是 77721876行。而我们通过在companyID和groupLabel两个字段上加上索引之后，扫描的行数只需要134行。在Mysql中可以通过 Explain Select来查看扫描次数。可以看出来在这种联表和复杂搜索条件的情况下，索引带来的性能提升远比它所占据的磁盘空间要重要得多。
那么索引是如何实现的呢？大多数DB厂商实现索引都是基于一种数据结构——B树。oracle实现索引的数据结构是B*树。具体关于B树、B+树、B*树的讲解可以查看另一篇博文：
树
可以看到在这棵B树搜索英文字母复杂度只为o(m)，在数据量比较大的情况下，这样的结构可以大大增加查询速度。然而有另外一种数据结构查询的虚度比B树更快——散列表。Hash表的定义是这样的：设所有可能出现的关键字集合为u，实际发生存储的关键字记为k，而|k|比|u|小很多。散列方法是通过散列函数h将u映射到表T[0,m-1]的下标上，这样u中的关键字为变量，以h为函数运算结果即为相应结点的存储地址。从而达到可以在o(1)的时间内完成查找。
然而散列表有一个缺陷，那就是散列冲突，即两个关键字通过散列函数计算出了相同的结果。设m和n分别表示散列表的长度和填满的结点数，n/m为散列表的填装因子，因子越大，表示散列冲突的机会越大。
因为有这样的缺陷，所以数据库不会使用散列表来做为索引的默认实现，Mysql宣称会根据执行查询格式尝试将基于磁盘的B树索引转变为和合适的散列索引以追求进一步提高搜索速度。我想其它数据库厂商也会有类似的策略，毕竟在数据库战场上，搜索速度和管理安全一样是非常重要的竞争点。
借鉴博客：
https://blog.csdn.net/qq_26222859/article/details/80631121