MySQL对索引的定义是：索引是一个数据结构，用于帮助MySQL高效地获取数据。
数据库查询是数据库的核心功能之一，我们都希望查询速度尽可能快。因此，数据库系统的设计者会从查询算法的角度进行优化。最基本的查询方法是顺序查找（linear search），其复杂度为O(n)，在数据量较大时显然不够理想。幸运的是，计算机科学的发展提供了许多更优秀的查找算法，如二分查找（binary search）和二叉树查找（binary tree search）。然而，每种查找算法只能应用于特定的数据结构。例如，二分查找要求数据是有序的，而二叉树查找只能在二叉查找树上进行。由于数据本身的组织结构无法完全满足各种要求，数据库系统会维护特定的数据结构，这些结构通过某种方式引用数据，从而在这些数据结构上实现更高级的查找算法。这种数据结构即为索引。
举个例子：
图1展示了一种可能的索引方式。左侧是数据表，共有两列七条记录，最左边是数据记录的物理地址（注意，逻辑上相邻的记录在磁盘上并不一定物理相邻）。为了加快对Col2的查找，可以维护一个右侧显示的二叉查找树，每个节点包含索引键值和指向对应数据记录物理地址的指针，这样可以在O(log2n)的复杂度内获取相应数据。尽管这是一种有效的索引方式，实际数据库系统几乎没有使用二叉查找树或其变种红黑树（red-black tree），原因将在后文中说明。
B-Tree和B+Tree
目前，大多数数据库系统和文件系统采用B-Tree或其变种B+Tree作为索引结构。接下来的部分将结合存储器原理与计算机存取原理，讨论B-Tree和B+Tree为何如此广泛应用于索引，而本节将从数据结构的角度描述它们。
B-Tree
B-Tree是一种多路搜索树（并非二叉树）：
- 任意非叶子节点最多有M个子节点，且M>2；
- 根节点的子节点数为[2, M]；
- 非根非叶子节点的子节点数为[M/2, M]；
- 每个节点存放至少M/2-1（向上取整）和至多M-1个关键字（至少2个关键字）；
- 非叶子节点关键字个数=指向子节点的指针个数-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]的子树，其余指针指向关键字属于(K[i-1], K[i])的子树；
- 所有叶子节点位于同一层；
- 每个k对应一个data。
例如（M=3）时，B-Tree相当于一个2-3树，每个节点要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且包含1个或2个数据元素。
B-树的搜索从根节点开始，利用节点内的关键字（有序）序列进行二分查找，如果找到则结束，否则进入查询关键字所属范围的子节点；重复此过程，直到找到对应的子指针为空或达到叶子节点。B-Tree上查找算法的伪代码如下：
BTree_Search(node, key) {
if(node == null) return null;
foreach(node.key)
{
if(node.key[i] == key) return node.data[i];
if(node.key[i] > key) return BTree_Search(point[i]->node);
}
return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);
B-树的特性包括：
- 关键字集合分布在整颗树中；
- 任何一个关键字只会出现在一个节点中；
- 搜索可能在非叶子节点结束；
- 其搜索性能等同于在关键字全集内进行一次二分查找；
- 自动层次控制。
B-树的自我控制：
B-树中的每个内部节点会包含一定数量的键值，通常数量在d与2d之间。在实际应用中，键值占用节点中大部分空间。因数2确保节点可以被拆分或合并。如果一个内部节点有2d个键值，添加一个新键值将导致拆分为两个d键值的节点，并将新键值添加到父节点。每个拆分的节点需要最小数量的键值。类似地，若一个内部节点和其相邻节点均有d个键值，则通过与邻居节点合并来删除一个键值，从而使该节点拥有d-1个键值；与邻居的合并将增加d个键值，加上从邻居节点的父节点移来的一个键值，最终形成完全填充的2d个键值。
B-树的构造过程：依次插入6, 10, 4, 14, 5, 11, 15, 3, 2, 12, 1, 7, 8, 8, 6, 3, 6, 21, 5, 15, 15, 6, 32, 23, 45, 65, 7, 8, 6, 5, 4。
B+Tree
B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL普遍使用B+Tree实现其索引结构。
与B-Tree相比，B+Tree的不同之处包括：
- 非叶子节点的子树指针与关键字个数相同；
- 非叶子节点的子树指针P[i]指向关键字值属于[K[i], K[i+1])的子树（B-树为开区间）；
- 所有叶子节点增加一个链指针；
- 所有关键字仅出现在叶子节点；
- 内部节点不存储data，仅存储key。
例如（M=3），B+的搜索与B-树基本相同，区别在于B+树只有达到叶子节点才命中（B-树可以在非叶子节点命中），其性能等同于在关键字全集做一次二分查找。
B+树的特性包括：
- 所有关键字在叶子节点的链表中出现（稠密索引），且链表中的关键字有序；
- 不可能在非叶子节点命中；
- 非叶子节点充当叶子节点的索引（稀疏索引），叶子节点则是存储（关键字）数据的层；
- 更适合文件索引系统。
B+树的构造过程：依次插入6, 10, 4, 14, 5, 11, 15, 3, 2, 12, 1, 7, 8, 8, 6, 3, 6, 21, 5, 15, 15, 6, 32, 23, 45, 65, 7, 8, 6, 5, 4。
索引的物理存储
一般而言，索引本身也很大，无法全部存储在内存中，因此索引通常以索引文件的形式存储在磁盘上。这样，在索引查找过程中会产生磁盘I/O消耗，相较于内存存取，I/O存取的消耗要高几个数量级。因此，评价一个数据结构作为索引的优劣，最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织应尽量减少查找过程中磁盘I/O的存取次数。
B-tree
假设每个盘块可以正好存放一个B树的节点（正好存放2个文件名）。那么一个BTNODE节点就代表一个盘块，而子树指针存放另一个盘块的地址。
接下来，我们模拟查找文件29的过程：
- 根据根节点指针找到文件目录的根磁盘块1，将信息导入内存。【磁盘IO操作 1次】
- 此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法发现：17<29<35，因此找到指针p2。
- 根据p2指针定位到磁盘块3，并将信息导入内存。【磁盘IO操作 2次】
- 此时内存中有两个文件名26、30和三个存储其他磁盘页面地址的数据。根据算法发现：26<29<30，因此找到指针p2。
- 根据p2指针定位到磁盘块8，并将信息导入内存。【磁盘IO操作 3次】
- 此时内存中有两个文件名28、29。根据算法查找到文件名29，并定位到该文件的磁盘地址。
从上述过程分析，我们发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是有序表结构，可以利用折半查找提高效率。而I/O操作是影响整个B树查找效率的关键因素。
如果我们使用平衡二叉树的磁盘存储结构进行查找，可能需要4次，最多5次磁盘I/O操作，而随着文件数量增加，B树所需的磁盘I/O操作次数将显著低于平衡二叉树，效率也更高。
B+Tree
B+树的优点包括：
- B+-tree的磁盘读写代价更低。由于B+-tree的内部节点没有指向关键字具体信息的指针，因此其内部节点相对B树更小。如果将所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，能一次性读入内存中的需要查找的关键字也就越多，因此I/O读写次数降低。
- B+-tree的查询效率更加稳定。由于非终结点不直接指向文件内容，查找关键字必须经过从根节点到叶子节点的路径，因此所有关键字查询路径长度相同，导致每个数据的查询效率相当。
MySQL的两种存储引擎的索引存储机制
MyISAM索引实现
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存储数据记录的地址。假设表有三列，以Col1为主键，图示为MyISAM表的主索引（Primary key）。可以看到，MyISAM的索引文件仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有区别，只是主索引要求key唯一，而辅助索引的key可以重复。如果在Col2上建立辅助索引，则该索引结构如下图所示：
同样是B+Tree，data域保存数据记录的地址。因此，MyISAM的索引检索算法是首先按照B+Tree搜索算法查找索引，如果指定的Key存在，则取出其data域的值，再以data域的值为地址读取相应的数据记录。MyISAM的索引方式被称为“非聚集”的。
InnoDB索引实现
虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式与MyISAM截然不同。
第一个重大区别是InnoDB的数据文件本身就是索引文件。与MyISAM不同，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身按B+Tree组织，叶节点的data域保存完整的数据记录。这个索引的key是数据表的主键，因此InnoDB的表数据文件本身就是主索引。
上图为InnoDB主索引（同时也是数据文件）的示意，叶节点包含完整的数据记录。这种索引称为聚集索引。由于InnoDB的数据文件必须按主键聚集，因此InnoDB要求表必须有主键（MyISAM可以没有）。如果未显式指定主键，MySQL系统会自动选择一个可唯一标识数据记录的列作为主键；如果没有这样的列，MySQL自动为InnoDB表生成一个隐含字段作为主键，长度为6。
注意：
[[[IMG_1]]]
[[[IMG_2]]]
[[[IMG_3]]]
[[[IMG_4]]]
[[[IMG_5]]]
[[[IMG_6]]]
[[[IMG_7]]]
[[[IMG_8]]]
[[[IMG_9]]]
