mysql主键索引为什么快（mysql主键索引数据结构）

大家好，我是讯享网，很高兴认识大家。

MYSQL官方文档介绍索引是一种方便快速查询数据的数据结构。用我们生活中的例子来讲，索引就好比书的目录，如果没有目录，每次你想要查找某些内容，你必须从头开始查找，这样的效率极其低下。
索引一般比较大，所以大部分情况下索引是存在磁盘的索引文件上，也有可能是存在数据文件上。
索引的种类有很多：主键索引（这是最常见的一种索引，主键不能为空且必须唯一）、唯一索引（相对于主键索引，它的值可以为空）、全文索引（在char、varchar、text类型可以使用）、普通索引、前缀索引。按照列数来区分：单一索引、组合索引（多字段组成）

在讲解MYSQL索引的数据结构之前，我们先看看了解一下其他的数据结构，看看他们的优缺点进行对比。

2.1 二叉树

二叉树简单来说就是左节点大于右节点，在理想的情况下，他的查找速度就接近与二分法的性能O(log2n)。因为在内存排序的时间是非常快的，可以忽略不计，所以总的消耗时间就取决于IO的操作次数。二叉树查找速度取决树高,每次查询接口都是一次IO操作，也是性能的瓶颈所在。

2.2 平衡二叉树

平衡二叉树可以解决二叉树不稳定导致查询效率低下的缺点。平衡二叉树的特点：树的左右节点层级最高相差一层。在插入或者删除的情况下，通过左旋转或右旋转使得整个二叉树平衡，不会出现层级相差很多的情况。平衡二叉树的性能接近二分法查找O(log2n)。

平衡二叉树查找id为8的记录，只需要IO操作2次即可。但是仔细想一下，如果数据量很多呢？假设数据表有100W的数据，根据O(log2n)计算，大约需要20次IO操作。磁盘寻道大概需要10ms，总的查询时间为20 * 10 = 0.2，效率也比较低下。
还有就是平衡二叉树不支持范围查询，范围查询每次都需要从根节点遍历，效率及其低下。

2.3 B-树(改造二叉树成多叉树)

2.4 B+树（改造B-树）

结合了B-树的缺点进行改造，就诞生了B+树。B+树跟B-树的差异并不是很大，判断的依据很简单：节点是否存放数据。B+树存放数据的节点只有叶子节点，而且叶子结点双向指针连接，形成了双向有序链表。

讯享网

MYISAM引擎 (主键索引)

MYISAM引擎是非聚簇索引，也就是说B+树的叶子节点的键值存放索引列的值，数据存在数据在磁盘的地址。MYISAM的索引文件跟数据文件是分开存储的。
studentidnameageididx_ageage
创建了一个表student，id为主键索引,age为普通索引。假设表中有以下数据，现在执行以下语句

具体链路：（实际上逻辑上相邻实际磁盘并不一定相邻，这里只是方便展示）
（1）先从磁盘1加载数据到内存，因为18>16走左路（一次IO操作）（2）读取磁盘2加载数据到内存，又因为16>14向下继续读取（一次IO操作）（3）检索叶子节点，判断到等于16则停止（一次IO操作）

MYISAM引擎 (辅助索引)

在MYISAM引擎中，主键索引跟辅助索引的差别并不很大，叶子节点存放的都是磁盘地址，只是辅助索引并并不是唯一值，所以在等值查询检索叶子节点的时候，也要按照范围一样，进行检索数据。

Innodb引擎（聚簇索引、主键索引）

具体链路：（实际上逻辑上相邻实际磁盘并不一定相邻，这里只是方便展示）

（1）先从磁盘1加载数据到内存，因为18<37走左路（一次IO操作）（2）读取磁盘2加载数据到内存，又因为37>24向下继续读取（一次IO操作）（3）检索叶子节点，判断到等于37则停止（一次IO操作）（4）这时候查到的数据就是age字段为37的记录主键值。按照聚簇索引的方式再查找数据就得到了数据结构集（这个过程叫做回表）相同索引字段情况下，按主键字段排序。因为要多加上三次回表操作，效率回相对低一点点。这里有个概念叫做覆盖索引，如果查询所需要的字段刚好就是索引字段就不需要回表查询，从而提高了查询效率。

索引的原理远远不止于这么一点点，组合索引以及一些其他的原理我暂时理解还不是到位，等到后面学习更加理解之后再写一篇文章进行记录总结吧。“学而不思则惘，思而不学则殆”，以前没办法理解这句话的涵义，直到后来才知道总结、思考才是学习最有效率的方式。多总结、多思考，也是作为一名程序员进步的最快方式。