概述：MySQL对索引的定义为：索引(Index)是帮助 MySQL 高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。我们清楚的知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search)，这种复杂度为 O(n) 的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如：二分查找(binary search)、二叉树查找(binary tree search)等。

  稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如：二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构，所以在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用(指向)数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构

B-Tree 在计算机科学中，B 树(英语：B-Tree)是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B 树，概括来说是一个一般化的二叉查找树(binary search tree)，可以拥有多于 2 个子节点。与自平衡二叉查找树不同，B 树为系统大块数据的读写操作做了优化。B 树减少定位记录时所经历的中间过程，从而加快存取速度。B 树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。B树是一种多路平衡搜索树(非二叉)，若其是 M 路，则：

 ♞ 任意非叶子节点最多可以有 M 个子女，且 M > 2；  ♞ 根节点的子女数为 [2，M]；  ♞ 除了根节点以外的非叶子节点的子女数目为 M / 2 (向上取整)个到 M 个；  ♞ 每个节点存放至少 M / 2-1 (向上取整)和至多 M - 1 个键值(至少两个)；  ♞ 非叶子节点的关键字个数 = 指向子女的指针个数 - 1；  ♞ 非叶子节点的关键字 K[1]，K[2]，··· ，K[M-1] 且有 K[i] < K[i+1]；  ♞ 非叶子节点的指针 P[1]，P[2]，··· ，P[M]；其中 P[1] 指向关键字小于 K[1] 的子树，P[M] 指向关键字大于 K[M-1] 的子树，其他 P[i] 指向关键字属于(K[i-1]，K[i])的子树；  ♞ 所有叶子节点都位于同一层。 B 树与二叉搜索树的最大区别在于其每个节点可以存不止一个键值，并且其子女不止两个，不过还是需要满足键值数 = 子女数 - 1。因此，对于相同数量的键值，B 树比二叉搜索树要更加矮一些，特别是当 M 较大时，树高会更低。

  每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个键将数据划分成的三个范围域，对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为 17 和 35，P1 指针指向的子树的数据范围为小于 17，P2 指针指向的子树的数据范围为 17~35，P3 指针指向的子树的数据范围为大于 35。模拟查找关键字 29 的过程：  ♞ 根据根节点找到磁盘块 1，读入内存。【磁盘第 1 次 IO 操作】  ♞ 比较关键字 29 在区间(17，35)，找到磁盘块 1 的指针 P2  ♞ 根据 P2 指针找到磁盘块 3，读入内存。【磁盘第 2 次 IO 操作】  ♞ 比较关键字 29 在区间(26，30)，找到磁盘块 3 的指针 P2  ♞ 根据 P2 指针找到磁盘块 8，读入内存。【磁盘第 3 次 IO 操作】  ♞ 在磁盘块 8 中的关键字列表中找到关键字 29 分析上面过程，发现需要 3 次磁盘 IO 操作，和 3 次内存查找操作，由于内存中的关键字是一个有序表结构，可以利用二分法快速定位到目标数据，而 3 次磁盘 IO 操作是影响整个 B-Tree 查找效率的决定因素。   MySQL 采用页方式来读写数据，每页是16KB，我们用 B 树来存储 MySQL 的记录，每个节点对应 MySQL 中的一页 16 KB，假如每行记录加上树节点中的 1 个指针占 160 Byte，那么每个节点可以存储 16 KB / 160 byte = 1000 条数据，树的高度为 3 的节点大概可以存储 1000(第一层) + 10002(第二层) + 10003(第三层) 条记录，即一个高度为 3 的 B 树大概可以存储 10 亿条记录，我们从 10 亿记录中查找数据只需要 3 次 IO 操作可以定位到目标数据所在的页，而页内部的数据又是有序的，然后将其加载到内存中用二分法查找，是非常快的。   可以看出使用 B 树定位某个值还是很快的，但是也是有缺点的 B 树不利于范围查找，比如上图中我们需要查找 [15，36] 区间的数据，需要访问 1、2、7、3、8、4、9 一共 7 个磁盘块，IO 次数又上去了，范围查找也是我们经常用到的，所以 b 树也不太适合在磁盘中存储需要检索的数据。

1.2.3 B+Tree

  B+ 树是 B 树的一种变形形式，B+ 树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵 m 阶的 B+ 树定义如下：  ♞ 每个结点至多有 m 个子女；  ♞ 除根结点外，每个结点至少有[m / 2]个子女，根结点至少有两个子女；  ♞ 有 k 个子女的结点必有 k 个关键字。 B+ 树的查找与 B 树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。

  在 B+Tree 的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的 B+Tree。做这个优化的目的是为了提高区间访问的性能，如果要查询 key 为从 15 到 36 的所有数据记录，当找到 15 后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。   B-Tree 因为非叶子结点也保存具体数据，所以在查找某个关键字的时候找到即可返回。而 B+Tree 所有的数据都在叶子结点，每次查找都得到叶子结点。所以在同样高度的 B-Tree 和 B+Tree 中，B-Tree 查找某个关键字的效率更高。B+Tree 所有的数据都在叶子结点，并且结点之间有指针连接，在找大于某个关键字或者小于某个关键字的数据的时候，B+Tree 只需要找到该关键字然后沿着链表遍历就可以了，而 B-Tree 还需要遍历该关键字结点的根结点去搜索。B-Tree 的每个结点都存储主键 + 实际数据，而 B+Tree 非叶子结点只存储关键字信息，而每个页的大小有限是有限的，所以同一页能存储的 B-Tree 的数据会比 B+Tree 存储的更少。这样同样总量的数据，B-Tree 的深度会更大，增大查询时的磁盘 IO 次数，进而影响查询效率。

索引是对数据库表中一列或多列的值进行排序的一种结构。索引只是提高效率的一个因素，如果你的MySQL有大数据量的表，就需要花时间研究建立最优秀的索引，或优化查询语句。了解索引，帮助我们更好的提高我们的代码运动速度。