MySQL（高级特性篇）06 章——索引的数据结构-EW帮帮网

一、为什么使用索引

索引是存储引擎用于快速查找数据记录的数据结构。查找数据时，先看查询条件是否命中索引，若命中则通过索引找数据；若未命中就需全表扫描，逐条查找符合条件的记录
图示：
在数据库无索引时，数据分散于硬盘不同位置，读取时摆臂摆动查找耗时；即便数据顺序摆放，按序读取也需多次 IO 操作，因涉及磁盘旋转及磁头寻道时间，其中磁头寻道速度慢、更耗时
假如给数据使用二叉树这样的数据结构进行存储，如下图所示：
对字段Col 2添加索引，即在硬盘为其维护二叉搜索树结构。树节点以<Col 2值, 行文件指针> 存储。查找Col 2 = 89记录时，通过二叉树遍历查找，如先读根节点34，因89＞34转右侧，再读89匹配成功，依节点value定位记录地址，仅两次查找便完成，大幅提升查询速度
建索引的目的就是为了减少磁盘I/O的次数，加快查询速率

二、索引及其优缺点

（1）索引概述

索引（Index）的作用：索引能帮助 MySQL 高效获取数据
索引的本质：索引是一种可理解为 “排好序的快速查找数据结构” 的数据结构
索引与存储引擎的关系：索引由存储引擎实现，不同存储引擎支持的索引不同，不一定支持所有索引类型，且可定义每个表的最大索引数和最大索引长度

（2）优点

性能优化：减少磁盘的I/O次数
数据约束：通过创建唯一索引，保证数据库表中每行数据的唯一性
连接加速：可以加速表和表之间的连接，提高联合查询的速度
分组排序优化：在使用分组和排序子句查询数据时，能显著减少分组和排序的时间（因为索引是排好序的快速查找数据结构）

（3）缺点

时间成本：创建和维护索引耗费时间
空间占用：索引占用磁盘空间，大量索引时，索引文件可能更快达最大文件尺寸
性能影响：索引提升查询速度，但降低表更新速度，表数据变化时索引需动态维护
优化建议：当索引影响插入记录速度时，可先删索引，插入数据后再创建索引

三、InnoDB中索引的推演

（1）索引之前的查找

先来看一个精确匹配的例子:

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

3.1.1在一个页中的查找

当表中记录少且可存于一个页时，查找记录根据搜索条件不同分两种情况：

以主键为搜索条件：可在页目录用二分法定位槽，再遍历对应分组记录快速找到指定记录
以其他列为搜索条件：数据页未对非主键列建页目录，无法用二分法定位，只能从最小记录开始遍历单链表并对比，查找效率低

3.1.2在很多页中查找

当表中记录多需多个数据页存储时，在多页中查找记录分两步：

查找步骤：先定位记录所在页，再从该页内查找对应记录
无索引情况：无论按主键列还是其他列查找，无法快速定位记录所在页，只能沿双向链表逐页查找，遍历所有页，耗时极长
索引出现：为解决无索引查找效率低的问题，索引应运而生

（2）设计索引

建一个表：

CREATE TABLE index_demo(
c1 INT,
c2 INT,
c3 CHAR(1),
PRIMARY KEY(c1)
) ROW_FORMAT = Compact;##ROW_FORMAT--行格式

这里我们简化了index_demo表的行格式示意图：
我们只在示意图里展示记录的这几个部分：
1. record_type：表示记录的类型，0表示普通记录，2表示最小记录，3表示最大记录
2. next_record：表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁
3. 各个列的值：这里只记录在index_demo表中的三个列，分别是c1、c2和c3
4. 其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息
将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样：
把一些记录放到页里的示意图就是下面这个基本的数据页模型：

3.2.1一个简单的索引设计方案

如果我们想快速定位到需要查找的记录在哪些数据页中该咋办？我们可以为快速定位记录所在的数据页建立一个目录，建这个目录必须完成下边这些事（该例索引建立在主键上）：
下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值
1. 假设：每个数据页最多能存放3条记录(实际上一个数据页非常大，可以存放下好多记录)。有了这个假设之后我们向index_demo表插入3条记录：
```
INSERT INTO index_demo VALUES (1,4,'u'),(3,9,'d')，(5,3,'y');
```
2. 那么这些记录已经按照主键值的大小串联成一个单向链表了，如图所示:
3. 从图中可以看出来, index_demo表中的3条记录都被插入到了编号为10的数据页中了。此时再来插入一条记录：
```
INSERT INTO index _demo VALUES(4,4,'a');
```
4. 因为页10最多只能放3条记录，所以我们不得不再分配一个新页：
5. 新分配的数据页编号可能不连续，通过维护上下页编号建立双向链表关系。若出现下一页中用户记录主键值小于上一页的情况（如页10最大主键值5，页28有主键值4的记录），插入该记录时需进行记录移动（将主键值5的记录移到页28，再把主键值4的记录插入页10），还有此过程的示意图：
6. 在对页中记录进行增删改操作时，需通过记录移动等操作保证下一个数据页中用户记录主键值大于上一个页中用户记录主键值，此过程称为页分裂
给所有的页建立一个目录项
1. 由于数据页的编号可能是不连续的，所以在向index_demo表中插入许多条记录后，可能是这样的效果:
2. 因为这些16KB的页在物理存储上是不连续的，所以如果想从这么多页中根据主键值快速定位某些记录所在页，需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：
  1. 页的用户记录中最小的主键值，用key来表示
  2. 页号，用page_no表示
3. 所以为上面几个页做好的目录就像这样子：
4. 目录项存储与功能：目录项包含对应页的页号及该页用户记录最小主键值，将目录项在物理存储器上连续存储（如用数组），可实现根据主键值快速查找记录
5. 查找示例：查找主键值为20的记录，先通过二分法在目录项中确定其对应目录项3（因 12 < 20 < 209）及页9，再按页中查找记录的方式在页9定位具体记录

3.2.2InnoDB中的索引方案

（1）迭代1次：目录项记录的页

简易索引方案问题：简易索引方案假设目录项物理上连续存放以用二分法查找，但存在问题。一是InnoDB以页管理存储空间，最多保证16KB连续空间，表记录增多时无法提供足够连续空间存放所有目录项；二是对记录增删时，如删除页中所有记录，需移动后续目录项，操作效率差
目录项记录区分：需灵活管理目录项，目录项记录与用户记录类似，包含主键和页号。InnoDB通过记录头里的record_type属性区分普通用户记录和目录项记录，其取值0代表普通用户记录，1代表目录项记录，2代表最小记录，3代表最大记录
现在把上面使用到的目录项放到数据页中的样子就是这样：
从图中可以看出来，新分配了一个编号为30的页来专门存储目录项记录
目录项记录和普通的用户记录的不同点：
1. record_type值不同，目录项记录为1，普通用户记录为0
2. 列的构成不同，目录项记录仅含主键值和页编号两列，普通用户记录列由用户自定义且可能含多列及InnoDB 添加的隐藏列；此外，存储目录项记录的页中主键值最小的目录项记录min_rec_mask值为 1，其他记录为 0
目录项记录和普通的用户记录的相同点：两者使用相同的数据页，都会为主键值生成Page Directory，按主键值查找时可用二分法加速查询
索引构建思路：可将多个记录分页，为每个页建立目录项

（2）迭代2次：多个目录项记录的页

目录项存储限制：目录项记录虽比用户记录所需存储空间小，但因数据页（16KB）容量有限，能存放的目录项记录数量受限
这里假设一个存储目录项记录的页最多只能存储4条目录项记录，所以如果此时再向上图中插入一条主键值为320的用户记录的话，那就需要分配一个新的存储目录项记录的页：
新记录插入处理：若表数据过多，一个数据页无法存放所有目录项记录，插入新记录时需分配新的数据页。如插入主键值为320的用户记录，需新生成存储该记录的页31，且因原存储目录项记录的页 30 容量满（假设最多存 4 条），需新的页 32 存放页 31 对应的目录项
多目录项页查找步骤：当存储目录项记录的页不止一个时，按主键值查找用户记录大致分三步，以查找主键值为 20 的记录为例：
1. 先确定目录项记录页（主键 20 对应的目录项记录在页 30，因页 30 目录项主键值范围是 [1, 320) ）
2. 再通过目录项记录页确定用户记录真实所在的页
3. 最后在真实存储用户记录的页中定位具体记录
数据库查询优化原则：在MySQL中，树的高度越低，查询时磁盘的 I/O 次数越少，查询效率越高。这是因为每次访问磁盘读取数据页都需要一定的时间开销，树高度降低意味着需要访问的数据页数量减少，从而减少了 I/O 次数，加快了查询速度

（3）迭代3次：目录项记录页的页

在MySQL中，当表数据量极大，产生众多存储目录项记录的页且这些页不连续时，按主键值查找用户记录的第一步需定位存储目录项记录的页。为了能快速根据主键值定位该页，会为存储目录项记录的页生成更高级的目录，类似多级目录结构，大目录嵌套小目录，小目录包含实际数据：
为快速定位存储目录项记录的页，生成了存储更高级目录项的页33，该页两条记录分别对应页30和页32。当用户记录主键值在[1, 320)时，去页30查详细目录项记录；主键值不小于 320时，去页32查找
可以用下边这个图来描述它：
该数据结构称为B+树

（4）B+Tree

B+树节点构成与连接：在数据库中，存放用户记录和目录项记录的数据页构成B+树，这些数据页称为节点。数据页内记录用单向链表连接，数据页间用双向链表连接。实际用户记录存于B+树最底层的叶子节点，其余存放目录项记录的为非叶子节点，最上边的是根节点
B+树节点分层规则：B + 树节点可分层，规定存放用户记录的最底层为第 0 层，依次往上递增，假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录，所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录，那么：
1. 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放100条记录
2. 如果B+树有2层，最多能存放 1000×100=10,0000 条记录
3. 如果B+树有3层，最多能存放 1000×1000×100=1,0000,0000 条记录
4. 如果B+树有4层，最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。相当多的记录！！！
也就是说，每层超过1页，就要对页创建目录项记录
B+树查询效率：一般情况下数据库使用的B+树不超 4 层，通过主键查找记录最多进行4次页面内查找（3 个目录项页和 1 个用户记录页），借助页目录在页面内可用二分法快速定位记录

（3）常见索引概念

索引按照物理实现方式，索引可以分为2种：聚簇（聚集）和非聚簇（非聚集）索引。也可以把非聚集索引称为二级索引或者辅助索引

3.3.1聚簇索引

聚簇索引的定义：是一种数据存储方式，索引即数据、数据即索引，所有用户记录存于B+树叶子节点
特点：
1. 排序规则：按记录主键值对记录和页排序，页内记录按主键大小成单向链表，存放用户记录的页及同一层次存放目录项记录的页按主键大小成双向链表
2. 数据存储：B+树叶子节点存储包含所有列值（含隐藏列）的完整用户记录
3. 自动创建：InnoDB存储引擎会自动创建聚簇索引，无需显式用Index语句
优点：
1. 访问速度快：索引和数据存于同一B+树，获取数据无需回表，比非聚簇索引更快
2. 主键操作高效：对主键的排序查找和范围查找速度快
3. 节省IO：查询一定范围数据时，因数据紧密相连，可节省大量IO操作
缺点：
1. 插入依赖顺序：当按照主键顺序插入数据时，新记录会被顺序添加到已有数据之后，通常不会引起页分裂；而如果不按主键顺序插入，可能会导致需要在已有的数据页中间插入新记录，当该数据页没有足够空间时，就会触发页分裂操作，将原数据页的部分记录移动到新的数据页，这会带来额外的开销，严重影响插入性能
2. 更新代价高：更新主键会导致行移动，代价高，所以InnoDB表主键一般不可更新
3. 二级索引需回表：二级索引访问需两次索引查找，即先找主键值，再根据主键值找行数据
限制：
1. MySQL中仅InnoDB支持聚簇索引，MyISAM不支持
2. 每个MySQL表只能有一个聚簇索引，通常是表的主键
3. 无主键时，InnoDB选非空唯一索引代替；无此类索引则隐式定义主键作聚簇索引，且主键列建议用有序顺序ID，避免用无序ID（如UUID等）

3.3.2二级索引（辅助索引、非聚簇索引）

聚簇索引的局限性：仅在搜索条件为主键值时才能发挥作用，若以其他列作为搜索条件，只能通过沿链表遍历记录的低效方式查找
解决方案：可构建多棵B+树，不同B+树采用不同排序规则，如以c2列大小对数据页和页中记录排序来构建新的B+树
与聚簇索引的不同：
1. 排序规则：此 B+ 树按记录c2列大小对记录和页排序，包括页内记录、存放用户记录的页以及同一层次存放目录项记录的页，分别按c2列大小排成单向或双向链表
2. 叶子节点存储内容：叶子节点仅存储c2列和主键列的值，而非完整用户记录
3. 目录项记录搭配：目录项记录为c2列与页号的搭配，而非主键与页号
使用场景：可通过该B+树以c2列的值为搜索条件查找记录
查找过程：以查找c2列值为4的记录为例，先根据根页面确定目录项记录所在页，再通过目录项记录页确定实际存储用户记录的页（因c2列无唯一性约束，记录可能分布在多个页），最后在这些页中定位具体记录
回表操作：该B+树叶子节点仅存储c2列和主键列，要获取完整用户记录，需根据主键值到聚簇索引中再次查找，此过程称为回表
存储权衡：若将完整用户记录放于叶子节点可避免回表，但会大幅增加存储空间，造成浪费
索引类型：这种按非主键列建立、需回表操作才能定位完整用户记录的B+树，被称为二级索引或辅助索引
非聚簇索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个非聚簇索引：
小结：
1. 存储内容差异：聚簇索引的叶子节点直接存储数据记录；非聚簇索引的叶子节点存储数据位置，且不影响数据表的物理存储顺序
2. 索引数量限制：一个表只能有一个聚簇索引，因为数据表的物理排序存储方式唯一；但可以有多个非聚簇索引，它们如同多个索引目录用于数据检索
3. 操作效率对比：使用聚簇索引进行数据查询时效率较高，无需回表操作；但在进行插入、删除、更新等数据操作时，其效率低于非聚簇索引

3.3.3联合索引（属于非聚簇索引）

可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说想让B+树按
照c2和c3列的大小进行排序，这个包含两层含义：
1. 先把各个记录和页按照c2列进行排序
2. 在记录的c2列相同的情况下，采用c3列进行排序
为c2和c3列建立的索引的示意图如下：
如图所示，需要注意以下几点：
1. 每条目录项记录都由c2、c3、页号这三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序
2. B+树叶子节点处的用户记录由c2、c3和主键c1列组成
注意一点，以c2和c3列的大小为排序规则建立的B+树称为联合索引 ，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：
1. 建立联合索引只会建立如上图一样的1棵B+树
2. 为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树

（4）InnoDB的B+树索引的注意事项

3.4.1根页面位置万年不动

实际上B+树的形成过程是这样的：
1. 索引创建：在为MySQL表创建B+树索引（聚簇索引默认存在，无需人为创建）时，会同时创建一个根节点页面
2. 初始状态：当表中尚无数据时，每个B+树索引对应的根节点既不包含用户记录，也没有目录项记录
3. 数据插入初期：开始向表中插入用户记录时，这些记录会首先被存储到根节点中
4. 根节点空间耗尽后：当根节点的可用空间被全部占用，若继续插入记录，会将根节点中的所有记录复制到一个新分配的数据页（例如页a）
5. 页分裂操作：对新分配的页a执行页分裂操作，生成另一个新的数据页（例如页b）
6. 记录分配与根节点升级：新插入的记录会根据键值（聚簇索引中的主键值或二级索引中对应的索引列的值）大小，被分配到页a或者页b中。与此同时，根节点的角色会发生转变，升级为存储目录项记录的页
在MySQL的InnoDB存储引擎中，对于B+树索引有如下特性：一个B+树索引的根节点自创建后位置固定不会移动。当为表建立索引时，其根节点的页号会被记录在特定位置，后续 InnoDB存储引擎使用该索引时，会从这个固定位置获取根节点页号以访问索引。

3.4.2内节点中目录项记录的唯一性

B+树索引的内节点中目录项记录的内容是索引列＋页号的搭配，但是这个搭配对于二级索引来说有点不严谨。还拿index_dema表为例，假设这个表中的数据是这样的：
如果二级索引中目录项记录的内容只是索引列＋页号的搭配的话，那么为c2列建立索引后的B+树应该长这样：
为表的c2列建立二级索引对应的B+树后，若要新插入一条c1、c2、c3值分别为9、1、'c'的记录，会遇到问题。因为页3中目录项记录由c2 列和页号构成，且页3里两条目录项记录的c2 列值都是1，新记录c2列值同样为1，此时无法确定该将新记录放入页4还是页 5
为了让新插入记录能找到自己在哪个页里，需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以二级索引的内节点的目录项记录实际上是由三个部分构成的：
1. 索引列的值
2. 主键号
3. 页号
也就是把主键值也添加到二级索引内节点中的目录项记录了，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的，所以为c2列建立二级索引后的示意图实际上应该是这样子的：
在MySQL二级索引的B+树里插入记录 (9, 1, 'c') 时，因页3中目录项记录由c2 列、主键和页号构成，可先比较新记录与页3各目录项记录的c2列值，若 c2 列值相同则继续比较主键值，由于B+树同一层不同目录项记录的“c2 列+主键”值唯一，最终能定位唯一目录项记录，此例中确定新记录应插入页5

3.4.3一个页面最少存储两条记录

InnoDB的一个数据页至少存放两条记录

四、MyISAM中的索引方案

B+树索引适用存储引擎如表所示：

索引/存储引擎	MyISAM	InnoDB	Memory
B+Tree	支持	支持	支持

Innodb和MyISAM默认的索引是Btree索引（即B+树索引）；而Memory默认的索引是Hash索引

MyISAM引擎使用B+Tree作为索引结构，叶子节点的data域存放的是数据记录的地址

（1）MyISAM索引的原理

下图是MyISAM索引的原理图：
InnoDB索引特点：InnoDB采用“索引即数据”的方式，聚簇索引对应的B+树的叶子节点包含了所有完整的用户记录
MyISAM数据存储：
1. 数据文件（.MYD）：MyISAM将表中的记录按插入顺序存于数据文件（.MYD），该文件不划分数据页，记录数量无限制。由于插入时未按主键大小排序，不能使用二分法查找数据
2. 索引文件（.MYI）：MyISAM把索引信息存于索引文件（.MYI），会单独为表的主键创建索引，其索引叶子节点存储的是主键值与数据记录地址的组合，而非完整的用户记录
在MySQL的MyISAM存储引擎中：
1. 主键索引和二级索引在结构上并无差异
2. 二者的区别在于对键（key）的要求，主键索引要求键具有唯一性，而二级索引的键可以重复
3. MyISAM不存在聚簇索引和非聚簇索引的概念
如果在Col2上建立一个二级索引，则此索引的结构如下图所示：

（2）MyISAM与InnoDB对比

索引类型与查找方式：InnoDB有聚簇索引，根据主键值对聚簇索引一次查找就能获取对应记录；MyISAM无聚簇索引，所有索引相当于二级索引，查找时需回表操作
文件存储形式：InnoDB数据文件本身就是索引文件；MyISAM索引文件和数据文件分离，索引文件仅保存数据记录地址
非聚簇索引数据域：InnoDB非聚簇索引的data域存储对应记录的主键值，所有非聚簇索引都引用主键作为data域；MyISAM索引记录的是数据的地址
回表操作效率：MyISAM回表操作快，可依据地址偏移量直接到文件中取数据；InnoDB需先获取主键，再到聚簇索引中查找记录，虽速度也不慢，但不如 MyISAM 直接用地址访问
主键要求：InnoDB要求表必须有主键，若未显式指定，系统会自动选择非空且能唯一标识记录的列作为主键；若不存在此类列，会自动生成一个6字节长整型的隐含字段作为主键。MyISAM表可以没有主键
小结：
1. 主键长度影响：在InnoDB中，由于所有二级索引都引用主键索引，若使用过长字段作为主键，会导致二级索引占用空间过大，因此不建议使用过长字段作为主键
2. 主键单调性影响：InnoDB数据文件是B+树，使用非单调主键插入新记录时，数据文件为维持B+树特性需频繁进行分裂调整，效率低下；而自增字段作为主键是更好的选择

五、索引的代价

索引在空间和时间上都会有消耗：

空间上的代价：建立索引需要为其构建B+树，每个B+树节点是一个默认占用16KB存储空间的数据页，大型B+树由众多数据页组成，会占用大量存储空间
时间上的代价：对表中数据进行增删改操作时，需修改各个B+树索引；存储引擎要额外花费时间进行记录移位、页面分裂、页面回收等操作以维护节点和记录的排序；若建立多个索引，每个B+树都要进行维护，会影响性能

六、MySQL数据结构选择的合理性

从MySQL的角度讲，不得不考虑一个现实问题就是磁盘IO。如果能让索引的数据结构尽量减少磁盘IO，所消耗的时间也就越小

在关系型数据库中，索引通常非常大，数据量较大时索引大小可达几个G甚至更多。为减少索引在内存中的占用，索引存储在外部磁盘上。利用索引查询时，无法将整个索引加载到内存，只能逐一加载

那么MySQL衡量查询效率的标准就是IO磁盘次数

（1）全表遍历

（2）Hash结构

Hash称为散列函数，它可以大幅提升检索数据的效率
Hash算法是通过某种确定性的算法（比如MD5、SHA1、SHA2、SHA3）将输入转变为输出。相同的输入永远可以得到相同的输出
举例：如果想要验证两个文件是否相同，那么不需要把两份文件直接拿来比对，只需要让对方把Hash函数计算得到的结果告诉你即可，然后在本地同样对文件进行Hash函数的运算，最后通过比较这两个Hash函数的结果是否相同，就可以知道这两个文件是否相同
加速查找速度的数据结构。常见的有两类：
1. 树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是O(log2N)
2. 哈希，例如HashMap，查询/插入/修改/删除的平均时间复杂度都是O(1)
（1）采用Hash进行检索效率非常高，基本上一次检索就可以找到数据，（2）而B+树需要自顶向下依次查找，多次访问节点才能找到数据，中间需要多次IO操作，从效率来说Hash比 B+树更快
在哈希的方式下，一个元素k处于h(k)中，即利用哈希函数h，根据关键字k计算出槽的位置。函数h将关键字域映射到哈希表T[o…m-1]的槽位上
上图中哈希函数h有可能将两个不同的关键字映射到相同的位置，这叫做碰撞，在数据库中一般采用链接法来解决。在链接法中，将散列到同一槽位的元素放在一个链表中，如下图所示：
Hash结构效率高，那为什么索引结构要设计成树型呢？
1. 范围查询效率：Hash 索引仅适用于（=）（<>）和IN查询，进行范围查询时时间复杂度退化为O(n)；树型索引因“有序”特性，能保持O(log₂N)的高效率
2. 排序性能：Hash索引的数据存储无序，在使用ORDER BY时，需要对数据重新排序，而树型索引在排序方面更具优势
3. 联合索引查询：对于联合索引，Hash值是合并联合索引键后计算的，无法单独对一个键或部分索引键进行查询，树型索引则不存在此问题
4. 重复值影响：虽然等值查询时Hash索引通常效率更高，但当索引列重复值较多，发生 Hash冲突时，需遍历桶中行指针比较，效率降低，因此Hash索引一般不用于性别、年龄这类重复值多的列，树型索引受此影响相对较小
Hash索引适用存储引擎如表所示：

索引/存储引擎 MyISAM InnoDB Memory

HASH索引不支持不支持支持
Hash索引的适用性：
1. 适用场景举例：
  1. 键值型数据库：如Redis，其存储核心为Hash表
  2. MySQL临时表：MySQL的Memory存储引擎支持Hash存储，在需要查询临时表时，可选用该引擎并将字段设为Hash索引，尤其适用于字符串类型字段，经Hash计算可缩短长度；当字段重复度低且常进行等值查询时，采用 Hash 索引是不错的选择
采用自适应Hash索引目的是方便根据 SQL 的查询条件加速定位到叶子节点，特别是当B+ 树比较深的时候，通过自适应Hash索引可以明显提高数据的检索效率
可以通过innodb_adaptive_hash_index变量来查看是否开启了自适应 Hash，比如：

索引/存储引擎	MyISAM	InnoDB	Memory
HASH索引	不支持	不支持	支持

（3）二叉搜索树

如果利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的
二叉搜索树的特点：
1. 一个节点只能有两个子节点，也就是一个节点的度不能超过2
2. 左子节点<本节点、右子节点>=本节点，比我大的向右，比我小的向左
查找规则：先来看下最基础的二叉搜索树(Binary Search Tree)，搜索某个节点和插入节点的规则一样，假设搜索插入的数值为key：
1. 如果key大于根节点，则在右子树中进行查找
2. 如果key小于根节点，则在左子树中进行查找
3. 如果key等于根节点，也就是找到了这个节点，返回根节点即可
举个例子，对数列（34，22，89，5，23，77，91）创造出来的二分查找树如下图所示：
但是存在特殊的情况，就是有时候二叉树的深度非常大。比如给出的数据顺序是(5,22,23,34,77,89,91)，创造出来的二分搜索树如下图所示：
二分查找树性能差异：二分查找树在不同结构下性能不同，如有的树会退化成链表，时间复杂度变为O (n)。树的深度影响查找效率，深度小则比较次数少，能更快找到节点，如深度为 3的树最多3次比较，深度为7的树最多需 7 次比较
提高查询效率的方法：为提高查询效率需减少磁盘IO数，而减少磁盘IO次数的关键是降低树的高度，将“瘦高”的树结构变为“矮胖”，使树每层的分叉尽可能多

（4）AVL树

平衡二叉搜索树的提出与性质：为解决二叉查找树退化为链表的问题，提出平衡二叉搜索树（AVL树），它在二叉搜索树基础上增加约束，即要么为空树，要么左右子树高度差绝对值不超过1，且左右子树均为平衡二叉树
常见平衡二叉树及特点：常见的平衡二叉树有多种，如平衡二叉搜索树、红黑树、数堆、伸展树等。平衡二叉搜索树是最早提出的平衡二叉树，一般提及平衡二叉树常指它，其搜索时间复杂度为O(log₂n)
二叉树用于数据查询的问题：数据查询时间主要取决于磁盘I/O次数，即便采用平衡二叉搜索树改进二叉树，树的深度为O (log₂n)，当数据量n较大时，树的深度仍较高。比如下图的情况：
每访问一次节点就需要进行一次磁盘I/O操作，对于上面的树来说，最多需要进行5次I/O操作。虽然平衡二叉树的效率高，但是树的深度也同样高，这就意味着磁盘I/O操作次数多，会影响整体数据查询的效率
针对同样的数据，如果把二叉树改成M叉树（M>2）呢?当M=3时，同样的31个节点可以由下面的三叉树来进行存储：
可以看到此时树的高度降低了，当数据量N大的时候，以及树的分叉数M大的时候，M叉树的高度会远小于二叉树的高度(M>2)。所以，我们需要把树从"瘦高"变"矮胖”

（5）B-Tree

B树的英文是Balance Tree，也就是多路平衡查找树。简写为B-Tree（注意横杠表示这两个单词连起来的意思，不是减号）。它的高度远小于平衡二叉树的高度
B树的结构如下图所示：
B树是多路平衡查找树，每个节点最多包含M个子节点，M为B树的阶，磁盘块包含关键字和子节点指针，若有x个关键字则指针数为x+1。以100阶B树为例，3层最多可存储约100万索引数据。对于大量索引数据，B树结构很合适，因其树高度远小于二叉树
一个M阶的B树(M>2)有以下的特性：
1. 根节点：根节点的儿子数量范围是[2, M]
2. 中间节点：每个中间节点包含k-1个关键字和k个孩子（孩子数量=关键字数量+1），k 的取值范围是[ceil (M/2), M]
3. 叶子节点：叶子节点包含k-1个关键字且无孩子，k的取值范围是[ceil (M/2), M]
4. 关键字与指针关系：中间节点的关键字 Key [1], Key [2] … Key [k - 1] 按升序排序，k-1 个关键字划分出k个范围，对应k个指针P [1], P [2] … P [K]。P [1]指向关键字小于Key [1] 的子树，P [i]指向关键字属于（Key [i - 1], Key [i]）的子树，P [K]指向关键字大于 Key [k - 1]的子树
5. 叶子节点层次：所有叶子节点位于同一层
上面那张图所表示的B树就是一棵3阶的B树。可以看一下磁盘块2，里面的关键字为(8，12)，它有3个孩子(3，5)，(9，10)和(13，15)，能看到(3，5)小于8，(9，10)在8和12之间，而(13，15)大于12，刚好符合刚才给出的特征
然后来看一下如何用B树进行查找。假设想要查找的关键字是9，那么步骤可以分为以下几步：
1. 与根节点的关键字(17，35)进行比较，9小于17那么得到指针P1
2. 按照指针P1找到磁盘块2，关键字为(8，12)，因为9在8和12之间，所以得到指针P2
3. 按照指针P2找到磁盘块6，关键字为(9，10)，然后找到了关键字9
在B树搜索中，内存比较时间可忽略不计，而磁盘块I/O操作耗时多，是数据查找用时的关键因素。与平衡二叉树相比，B树磁盘I/O操作更少，数据查询效率更高。因此，降低树的高度、减少IO次数能够提高查询性能
小结：
1. 自平衡机制：当对B树进行插入或删除节点操作时，可能会破坏树的平衡状态。不过，B 树具备自动调整节点位置的能力，能及时恢复树的平衡结构
2. 数据分布特点：B树中的关键字集合分布于整棵树，无论是叶子节点还是非叶子节点都会存储数据。这意味着在进行数据搜索时，搜索过程有可能在非叶子节点就提前结束
3. 搜索性能表现：B树的搜索性能与在关键字全集内进行一次二分查找相当。这表明在 MySQL中使用B树作为索引结构时，可以在相对较少的比较次数内找到目标数据，从而有效减少了磁盘I/O操作，提高了数据查询的整体效率
再举例：

（6）B+Tree

B+树也是一种多路搜索树，基于B树做出了改进，主流的DBMS都支持B+树的索引方式，比如MySQL。相比于B-Tree，B+Tree适合文件索引系统
B+树和B树的差异：
1. 关键字与孩子节点数量关系：B+树中孩子数量等于关键字数；B树里孩子数量等于关键字数加1
2. 关键字存储特点：B+树中非叶子节点的关键字会同时出现在叶子节点中，且为叶子节点所有关键字中的最大（或最小）值
3. 节点数据保存情况：B+树的非叶子节点仅作索引，不保存数据，记录相关信息都存于叶子节点；B树的非叶子节点既保存索引也保存数据
4. 叶子节点特性：B+树中所有关键字都在叶子节点出现，叶子节点构成有序链表，且按关键字大小从小到大顺序连接
B+树相较于B树的优点：
1. 查询效率稳定性：（1）B+树：每次都需访问叶子节点才能找到对应数据，查询效率稳定（2）B树：非叶子节点也存储数据，可能在非叶子节点找到关键字，也可能需到叶子节点才能找到，查询效率不稳定
2. 查询效率高低：（1）B+树：非叶子节点不存储数据，相同大小页能存储更多目录项，树更矮胖（阶数大、深度低），查询所需磁盘I/O更少，查询效率更高（2）B树：非叶子节点存储数据，相同磁盘页大小下存储节点关键字数量相对较少，查询效率相对较低
3. 范围查询效率：（1）B+树：所有关键字在叶子节点，叶子节点有指针且数据递增，范围查找可通过指针连接进行，效率高（2）B树：需通过中序遍历完成范围查找，效率较低
思考题1：为了减少IO，索引树会一次性加载吗？答：数据库索引存于磁盘，数据量大会使索引超几个 G，利用索引查询时无法将全部索引加载进内存，只能逐一加载对应索引树节点的磁盘页
思考题2：B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO？答：InnoDB存储引擎页大小16KB，表主键和指针类型常见占用字节数下，一个页约存1K个键值，深度为3的 B+Tree 索引可维护10亿条记录。实际中节点可能填不满，数据库里B+Tree 高度一般2-4层，且InnoDB设计让根节点常驻内存，所以查找行记录最多只需1-3次磁盘 I/O 操作
思考题3：为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？答：
1. 查询效率方面：B+树非终结点仅为叶子结点关键字的索引，关键字查找需从根到叶子结点，所有查询路径长度相同，查询效率稳定且相当
2. 磁盘读写代价方面：B+树内部结点无指向关键字具体信息的指针，比B树内部结点小，同一盘块能容纳更多关键字，一次性读入内存的待查关键字增多，降低了IO读写次数
思考题4：Hash索引与B+树索引的区别？答：
1. 范围查询能力：Hash索引指向的数据无序，不能进行范围查询；B+ 树叶子节点是有序链表，可以进行范围查询
2. 联合索引使用情况：Hash索引计算Hash值时合并索引键，不支持联合索引的最左侧原则，部分索引无法使用；B+树可以支持
3. 排序与模糊查询：Hash索引指向的数据无序，不支持ORDER BY排序和模糊查询；B+ 树索引数据有序，可对字段进行ORDER BY排序优化，使用LIKE进行以 % 结尾的模糊查询时可起到优化作用
4. InnoDB 支持情况：InnoDB不支持哈希索引
思考题5：Hash 索引与B+树索引是在建索引的时候手动指定的吗？
1. 针对InnoDB和MyISAM存储引擎，都会默认采用B+树索引，无法使用Hash索引
2. InnoDB提供的自适应Hash是不需要手动指定的

（7）R树

R-Tree在MySQL中应用较少，仅支持geometry数据类型，且支持该类型的存储引擎有myisam、bdb、innodb、ndb、archive 。在现实中，如查找20英里内所有餐厅，若无R树，一般将餐厅坐标(x,y)分两个字段（经度、纬度）存于数据库，需遍历所有餐厅获取位置信息并计算是否满足要求，若地区有100家餐厅就要进行100次位置计算，在谷歌、百度地图这类超大数据库中此方法不可行。而R树能很好地解决这种高维空间搜索问题
R树将B树思想拓展到多维空间，沿用B树分割空间的思路，在添加、删除操作时通过合并、分解结点来维持树的平衡性，是用于存储高维数据的平衡树。相较于B树，R树在范围查找上具备明显优势
表格：

索引/存储引擎 MyISAM InnoDB Memory

R-Tree索引支持支持不支持

索引/存储引擎	MyISAM	InnoDB	Memory
R-Tree索引	支持	支持	不支持

（8）小结

索引的利弊及使用要点：索引能在海量数据中快速定位目标数据，提升查询效率，但存在占用存储空间、降低数据库写操作性能、多索引时增加索引选择时间等弊端。使用时需平衡提升查询效率的利与维护索引的代价
实际应用中的索引决策：实际工作里，要依据需求和数据分布情况来决定是否使用索引。尽管索引并非万能，但数据量大时，索引对提升数据检索效率极为关键，不使用索引难以想象

（9）算法的时间复杂度

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率
算法的时间复杂度总结：

MySQL（高级特性篇）06 章——索引的数据结构