本篇文章主要学习了MySQL的索引的数据结构的认识，做一个大概的了解即可。

一、索引

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储数据结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，可以根据目录中的页码快速查找到所需的内容。

在MySQL中，存储引擎用类似的方法使用索引，先在索引中找到对应值，然后根据匹配的索引记录找到对应的行。

首先说明下MySQL的索引主要是基于Hash表或者B 树。

二、索引数据结构

了解索引就需要从索引常见的数据结构开始了解学习，这里有集中常见的的索引数据结构。

二叉树（Binary Trees）

二叉树是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常被称之为“左子树”和“右子树”

左子树<父节点<=右子树

二叉树的第i层至多有有2^(i-1)个节点，

深度为K的二叉树至多总共有个2^k-1节点（定义根节点所在深度 k0=0），而总计拥有节点数符合的，称为“满二叉树”；

二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆，并应用于高效率的搜索和排序。

同时学习数据结构，这里还推荐Data Structure Visualizations进行学习，可以非常直观的看到数据结构允许的过程，一步一步的怎么走的都可以很清晰看得到。

找到其中的Binary Search Trees二叉树

可以直观的看到二叉树的数据插入过程，如下：

可以看到二叉树不适合用作当作索引的，数据量庞大的话，二叉树的层数会很大，查找效率固然也很慢了。

红黑树（Red-Black Trees）

是一种自平衡二叉查找树，典型用途是实现关联数组。

红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在O(log n)时间内完成查找，插入和删除，这里的n是树中元素的数目。

红黑树遵行以下原则：

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

下面是一个具体的红黑树的图例：

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

同样在Data Structure Visualizations中选择Red-Black Trees红黑树进行插入操作可以直观的看到红黑树的插入过程

同样红黑树也不适用于MySQL的索引，数据量庞大之后，数层也会变大。

其他结构的问题

由于无法装入内存，则必然依赖磁盘（或SSD）存储。而内存的读写速度是磁盘的成千上万倍（与具体实现有关），因此，核心问题是“如何减少磁盘读写次数”。

首先不考虑页表机制，假设每次读、写都直接穿透到磁盘，那么：

线性结构：读/写平均O(n)次
二叉搜索树（BST）：读/写平均O(log2(n))次；如果树不平衡，则最差读/写O(n)次
自平衡二叉搜索树（AVL）：在BST的基础上加入了自平衡算法，读/写最大O(log2(n))次
红黑树（RBT）：另一种自平衡的查找树，读/写最大O(log2(n))次

BST、AVL、RBT很好的将读写次数从O(n)优化到O(log2(n))；其中，AVL和RBT都比BST多了自平衡的功能，将读写次数降到最大O(log2(n))。

假设使用自增主键，则主键本身是有序的，树结构的读写次数能够优化到树高，树高越低读写次数越少；自平衡保证了树结构的稳定。如果想进一步优化，可以引入B树和B 树。

B树（B-Trees）

又称：多路平衡查找树。大多数存储引擎都支持B树索引。b树通常意味着所有的值都是按顺序存储的，并且每一个叶子节点到根的距离相同。B树索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取数据。下图就是一颗简单的B树。

在B树中，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。

如下图所示：

叶节点具有相同的深度，叶节点的指针为空
所有索引元素不重复
节点中的数据索引从左到右递增排列
无论中间节点还是叶子节点都带有卫星数据data（索引元素所指向的数据记录）

只演示了插入的过程，其中可以通过delete、find执行删除和查找操作。直观的感受到B树的执行过程。

每个节点存储了多个Key和子树，子树与Key按顺序排列。

同二叉搜索树类似，每个节点存储了多个key和子树，子树与key按顺序排列。

页表的目录是扩展外存加速磁盘读写，一个页（Page）通常4K（等于磁盘数据块block的大小，见inode与block的分析），操作系统每次以页为单位将内容从磁盘加载到内存（以摊分寻道成本），修改页后，再择期将该页写回磁盘。考虑到页表的良好性质，可以使每个节点的大小约等于一个页（使m非常大），这每次加载的一个页就能完整覆盖一个节点，以便选择下一层子树；对子树同理。对于页表来说，AVL（或RBT）相当于1个key 2个子树的B树，由于逻辑上相邻的节点，物理上通常不相邻，因此，读入一个4k页，页面内绝大部分空间都将是无效数据。

假设key、子树节点指针均占用4B，则B树节点最大m * (4 4) = 8m B；页面大小4KB。则m = 4 * 1024 / 8m = 512，一个512叉的B树，1000w的数据，深度最大 log(512/2)(10^7) = 3.02 ~= 4。对比二叉树如AVL的深度为log(2)(10^7) = 23.25 ~= 24，相差了5倍以上。震惊！B树索引深度竟然如此！

那为什么B数这么厉害了，还有B 树的出现呢，必然是解决B树存在的问题

1、为定位行数

2、无法处理范围查询

问题1：为定位行数

数据表的记录有多个字段，仅仅定位到主键是不够的，还需要定位到数据行。有3个方案解决：

直接将key对应的数据行（可能对应多行）存储子节点中。
数据行单独存储；节点中增加一个字段，定位key对应数据行的位置。
修改key与子树的判断逻辑，使子树大于等于上一key小于下一key，最终所有访问都将落于叶子节点；叶子节点中直接存储数据行或数据行的位置。

方案1直接pass，存储数据行将减少页面中的子树个数，m减小树高增大。

方案2的节点中增加了一个字段，假设是4B的指针，则新的m = 4 * 1024 / 12m = 341.33 ~= 341，深度最大 log(341/2)(10^7) = 3.14 ~= 4。

方案3的节点m与深度不变，但时间复杂度变为稳定的O(logm(n))。

方案3可以考虑。

问题2：无法处理范围查询

实际业务中，范围查询的频率非常高，B树只能定位到一个索引位置（可能对应多行），很难处理范围查询。改动较小的是2个方案：

不改动；查询的时候先查到左界，再查到右界，然后DFS（或BFS）遍历左界、右界之间的节点。
在“问题1-方案3”的基础上，由于所有数据行都存储在叶子节点，B树的叶子节点本身也是有序的，可以增加一个指针，指向当前叶子节点按主键顺序的下一叶子节点；查询时先查到左界，再查到右界，然后从左界到有界线性遍历。

乍一看感觉方案1比方案2好——时间复杂度和常数项都一样，方案1还不需要改动。但是别忘了局部性原理，不管节点中存储的是数据行还是数据行位置，方案2的好处在于，依然可以利用页表和缓存预读下一节点的信息。而方案1则面临节点逻辑相邻、物理分离的缺点。

B 树（B Trees）

主要变动如上所述：

修改key与子树的组织逻辑，将索引访问都落到叶子节点
按顺序将叶子节点串起来（方便范围查询）

回顾上一个B树，一个m阶的B树具有如下几个特征：

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

一个m阶的B 树具有如下几个特征：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B 树特性总结

B 树是B树的升级版，其有如下特性

非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接，提高区间访问的性能
只有叶子节点带有卫星数据data（索引元素所指向的数据记录）

同样在Data Structure Visualizations中选择B TreesB 树进行插入操作可以直观的看到插入过程

在动图中可以看出，B 树的每一个叶子节点都有一个指针指向下一个节点，把所有的叶子节点串在一起。索引数据都存储在叶子节点中。

B 树相比于B树，有什么优势呢：

1.单一节点存储更多的元素，使得查询的IO次数更少。

2.所有查询都要查找到叶子节点，查询性能稳定。

3.所有叶子节点形成有序链表，便于范围查询。

总结，B 树相比B树的优势有三：1.IO次数更少；2.查询性能稳定；3.范围查询简便。

Hash索引

hash索引基于hash表实现，Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中。只有精准匹配索引所有列的查询才有效。索引的检索可以一次定位，不像B-Tree索引需要从根节点出发到目标节点。虽然Hash索引很快，远高于B-tree索引，但是也有其弊端。

Hash索引仅仅能满足'=','IN','<=>'查询，也就是等值查询，不能使用范围查询。很受限
由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。
由于Hash索引是通过hash表实现，其本身是没有排序的。
由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算；
Hash索引不能利用部分索引键查询
对于组合索引，Hash索引在计算hash值的时候是组合索引键合并后再一起计算hash值，而不是单独计算hash值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。
Hash 索引在任何时候都不能避免表扫描
前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。
对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

三、MySQL数据库引擎

通过navicat工具查看表设计选项中，从引擎中可以看到MySQL又这么多引擎。具体细分到每个表，不同的表引擎可以不一样。

MyISAM

新建一张表t_test_myisam，引擎使用MyISAM，查看原文件可以看到有3个文件

可以看到索引和数据是分开的，其中索引文件仅仅保存数据记录的地址，故属于非聚簇索引。

主键索引（Primary Index）

MyISAM引擎使用B Tree作为索引结构，叶节点的data存放的是数据记录的地址。如下图是MyISAM主键索引的原理图。

其中Col1为主键，可以看出看出MyISAM的索引文件仅保存数据记录的地址。

辅助索引（Secondary Index）

在Col2上建立一个辅助索引，如下图辅助索引原理图。

可以看到与主键索引没有任何区别，只不过主键索引的key是唯一的，而辅助索引的key可以重复。

MyISAM中索引检索的算法为首先按照B Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

InnoDB

新建一张表t_test_innodb，引擎使用InnoDB，查看原文件可以看到有2个文件

主键索引（Primary Index）

InnoDB的索引和数据在一个文件当中。

按照B Tree组织的一个索引结构。

叶节点保存了完整的数据记录和索引。这种索引就叫做聚簇索引。

索引的Key是数据的主键，因此InnoDB表数据文件本身就是主索引。

如下图：

可以看到叶节点包含了完整的数据记录。

因为InnoDB的数据文件本身要按照主键聚集，所以InnoDB要求必须有主键。如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段rowid作为主键，这个字段长度为6个字节，类型为长整形。

辅助索引（Secondary Index）

辅助索引，将途中的第二行name，作为索引如图

聚簇索引这种实现方式使得按照主键的搜索十分高效，但是首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

由于InnoDB索引的实现特性，推荐使用整形的自增主键。

有三点好处：

自增key一般为int等整数型，key比较紧凑，这样m可以非常大，而且索引占用空间小。最极端的例子，如果使用50B的varchar（包括长度），那么m = 4 * 1024 / 54m = 75.85 ~= 76，深度最大log(76/2)(10^7) = 4.43 ~= 5，再加上cache缺失、字符串比较的成本，时间成本增加较大。同时，key由4B增长到50B，整棵索引树的空间占用增长也是极为恐怖的（如果二级索引使用主键定位数据行，则空间增长更加严重）。
MySQL索引底层的数据比较都是整数型比较，如果主键时字符串类型的，里面还有英文，还得转换ASCII码进行比较。所以不建议使用uuid作为主键。
自增的主键使得数据行的插入比如落到索引数的最右侧，发生节点分裂的频率较低。B Tree实际操作插入过程。如果不是非单调主键，插入过程很大程度会发生节点重排，不利于索引优化的初衷。

InnoDB索引和MyISAM索引的区别

一是主索引的区别：InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

四、覆盖索引

InnoDB存储引擎支持覆盖索引，即从辅助索引中就可以得到查询的记录，不需要查询聚簇索引中的记录了。可以减少大量的IO操作。

如果要查询辅助索引中不含有的字段，得先遍历辅助索引，再遍历聚集索引，而如果要查询的字段值在辅助索引上就有，就不用再查聚集索引了，这显然会减少IO操作。

五、联合索引

两个或以上的列上的索引。如下图联合索引的原理图：

上图中的联合索引有三个，从上到下，严格按照排序。

六、优化建议

最左前缀匹配

索引可以简单如一个列(a)，也可以复杂如多个列(a, b, c, d)，即联合索引。如果是联合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在（相等），遇到范围查询(>、<、between、like左匹配)等就不能进一步匹配了，后续退化为线性查找。因此，列的排列顺序决定了可命中索引的列数。

如有索引(a, b, c, d)，查询条件a = 1 and b = 2 and c > 3 and d = 4，则会在每个节点依次命中a、b、c，无法命中d。也就是最左前缀匹配原则。

=、in自动优化顺序

不需要考虑=、in等的顺序，mysql会自动优化这些条件的顺序，以匹配尽可能多的索引列。

如有索引(a, b, c, d)，查询条件c > 3 and b = 2 and a = 1 and d < 4与a = 1 and c > 3 and b = 2 and d < 4等顺序都是可以的，MySQL会自动优化为a = 1 and b = 2 and c > 3 and d < 4，依次命中a、b、c。

索引列不能参与计算

有索引列参与计算的查询条件对索引不友好（甚至无法使用索引），如from_unixtime(create_time) = '2014-05-29'。

原因很简单，如何在节点中查找到对应key？如果线性扫描，则每次都需要重新计算，成本太高；如果二分查找，则需要针对from_unixtime方法确定大小关系。

因此，索引列不能参与计算。上述from_unixtime(create_time) = '2014-05-29'语句应该写成create_time = unix_timestamp('2014-05-29')。

能扩展就不要新建索引

如果已有索引(a)，想建立索引(a, b)，尽量选择修改索引(a)为索引(a, b)。

新建索引的成本很容易理解。而基于索引(a)修改为索引(a, b)的话，MySQL可以直接在索引a的B 树上，经过分裂、合并等修改为索引(a, b)。

不需要建立前缀有包含关系的索引

如果已有索引(a, b)，则不需要再建立索引(a)，但是如果有必要，则仍然需考虑建立索引(b)。

性能调优-MySQL索引数据结构详解与索引优化