MySQL详解：索引的介绍和原理分析 _MySQL详解

索引的定义MySQL官方对索引的定义为：索引（Index）是协助MySQL高效获取数据的数据结构。
本质上，索引的目的是为了提高查询效率，通过不断地缩小想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是说，有了这种索引机制，我们可以总是用同一种查找方式来锁定数据。
可以类比银行的保险柜，比如你要找归属你的保险柜子。如果没有索引，你需要拿着钥匙，一个个的保险柜的试过去才能找到属于你的保险柜。但是如果有了索引，而且保险柜能够以物理分区的方式存在在对应的区域，同时你可以根据钥匙上的编号（A1003-10-17），找到保险柜所在 A1003的存放房间，找到存放室保险柜的第10排，再找到第17个位置，找到属于你的保险柜，这个定位就快很多了。在没有索引的情况下，要想完成这个事情还是比较困难的。
索引的原理除了保险柜之外，生活中可以引出很多类似的索引例子，如字典词典的目录、图书馆的检索录、火车的座次表等。
它们的原理一致：不断地缩小数据范围来筛选数据，并把随机数据变成顺序数据，方便我们更快地锁定数据。
这种索引的理解同样适用我们的数据库查询，但是数据库会有很多更复杂的情况，除了等值查询外，还有范围查询(>、<、between、in)、模糊查询(like)、并集查询(or)、交集查询（and）等等。这就要求数据库选择更加复杂和成熟的方式来应对所有问题。
根据我们上面保险柜的案例，可以对数据按照一定规则进行拆分，这样匹配的范围就降低了，但是这远远不够满足数据库复杂的查询要求。于是，数据库系统的设计者从查询算法的角度进行优化。
其中最基本的查询算法是顺序查找（linear search），这种算法复杂度为O(n)，在数据量很大时就很不理想了，而且数据量越大，计算越复杂。
但没关系，强大的计算机科学提供了更多优秀的查找算法，比如二分查找（binary search）、二叉树查找（binary tree search）等。
但是这些查找算法都要求应用于特定的数据结构之上，如二分查找要求被检索数据有序，而二叉树查找只能基于二叉查找树结构上操作，数据本身的组织结构不可能完全满足各种数据结构，理论上也无法同时要求将多列都按顺序进行组织。
因此，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
这与上面MySQL官方对索引的定义遥相呼应了。
看下面的图：

文章插图

图举例了一种索引方式。右边是一个数据表，这边一共模拟了两列七行的数据，字段1 的是数据记录的物理地址（实际应用中逻辑上相邻的记录在磁盘上并不一定物理相邻，这边主要为了举例）。为了加快字段2 的查找，可以维护一个左边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)O(log2n)的复杂度内获取到相应数据。
这是索引的一种表现形式，但是实际的数据库系统中比较普遍是采用B+树来实现的。B+树中的B代表平衡（balance），不是二叉（binary）。因为B+树是从最早的平衡二叉树演化而来的，所以我们可以先了解下二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree），因为B+树是由这些树逐步演进而来。
二叉查找树二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。所以左中右是依次递增的一个过程。
如下图所示就是一棵二叉查找树，

文章插图

观察该二叉树有有如下发现，深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3+3) / 7 = 2.4次。
二叉查找树也可以是如下结构（同样满足二叉树左 < 中 < 大的特性），同样是7,21,35,42,51,77,89 这七个数字，也可以按照下图的方式来构造：