MySQL索引

1、Mysql如何实现的索引机制？

MySQL中索引分三类：B+树索引、Hash索引、全文索引

2、InnoDB索引与MyISAM索引实现的区别是什么？

MyISAM的索引方式都是非聚簇的，与InnoDB包含1个聚簇索引是不同的。

• 在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM中却需要进行一次回表操作，意味着MyISAM中建立的索引相当于全部都是二级索引 。

• InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的 ，索引文件仅保存数据记录的地址。

  • MyISAM的表在磁盘上存储在以下文件中： *.sdi（描述表结构）、*.MYD（数据），*.MYI（索引）

  • InnoDB的表在磁盘上存储在以下文件中： .ibd（表结构、索引和数据都存在一起）

• InnoDB的非聚簇索引data域存储相应记录主键的值 ，而MyISAM索引记录的是地址 。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。

• MyISAM的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。

• InnoDB要求表必须有主键 （ MyISAM可以没有 ）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

3、一个表中如果没有创建索引，那么还会创建B+树吗？

会

• 如果有主键会创建聚簇索引

• 如果没有主键会生成rowid作为隐式主键

4、说一下B+树索引实现原理（数据结构）

讲义

假设有一个表index_demo，表中有2个INT类型的列，1个CHAR(1)类型的列，c1列为主键：

CREATE TABLE index_demo(c1 INT,c2 INT,c3 CHAR(1),PRIMARY KEY(c1)) ;

index_demo表的简化的行格式示意图如下：

我们只在示意图里展示记录的这几个部分：

• record_type：表示记录的类型， 0是普通记录、 2是最小记录、 3 是最大记录、1是B+树非叶子节点记录。

• next_record：表示下一条记录的相对位置，我们用箭头来表明下一条记录。

• 各个列的值：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3 。

• 其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

将其他信息项暂时去掉并把它竖起来的效果就是这样：

把一些记录放到页里的示意图就是（这里一页就是一个磁盘块，代表一次IO）：

name age sex

MySQL InnoDB的默认的页大小是16KB，因此数据存储在磁盘中，可能会占用多个数据页。如果各个页中的记录没有规律，我们就不得不依次遍历所有的数据页。如果我们想快速的定位到需要查找的记录在哪些数据页中，我们可以这样做 ：

• 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值

• 给所有的页建立目录项

以页28为例，它对应目录项2 ，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值 5。我们只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。比如：查找主键值为 20 的记录，具体查找过程分两步：

1. 先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为 12 ≤ 20 < 209 ），对应页9。

2. 再到页9中根据二分法快速定位到主键值为 20 的用户记录。

至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为索引 。

InnoDB中的索引方案

我们新分配一个编号为30的页来专门存储目录项记录，页10、28、9、20专门存储用户记录：

目录项记录和普通的用户记录的不同点：

• 目录项记录 的 record_type 值是1，而 普通用户记录 的 record_type 值是0。

• 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，包含很多列，另外还有InnoDB自己添加的隐藏列。

现在查找主键值为 20 的记录，具体查找过程分两步：

1. 先到页30中通过二分法快速定位到对应目录项，因为 12 ≤ 20 < 209 ，就是页9。

2. 再到页9中根据二分法快速定位到主键值为 20 的用户记录。

更复杂的情况如下：

我们生成了一个存储更高级目录项的 页33 ，这个页中的两条记录分别代表页30和页32，如果用户记录的主键值在 [1, 320) 之间，则到页30中查找更详细的目录项记录，如果主键值 不小于320 的话，就到页32中查找更详细的目录项记录。这个数据结构，它的名称是 B+树 。

5、聚簇索引与非聚簇索引b+树实现有什么区别？

聚簇索引

特点：

• 索引和数据保存在同一个B+树中

• 页内的记录是按照主键的大小顺序排成一个单向链表 。

• 页和页之间也是根据页中记录的主键的大小顺序排成一个双向链表 。

• 非叶子节点存储的是记录的主键+页号。

• 叶子节点存储的是完整的用户记录。

优点：

• 数据访问更快 ，因为索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快。

• 聚簇索引对于主键的排序查找和范围查找速度非常快。

• 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库可以从更少的数据块中提取数据，节省了大量的IO操作 。

缺点：

• 插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键。

• 更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。

限制：

• 只有InnoDB引擎支持聚簇索引，MyISAM不支持聚簇索引。

• 由于数据的物理存储排序方式只能有一种，所以每个MySQL的表只能有一个聚簇索引。

• 如果没有为表定义主键，InnoDB会选择非空的唯一索引列代替。如果没有这样的列，InnoDB会隐式的定义一个主键作为聚簇索引。

• 为了充分利用聚簇索引的聚簇特性，InnoDB中表的主键应选择有序的id，不建议使用无序的id，比如UUID、MD5、HASH、字符串作为主键，无法保证数据的顺序增长。

非聚簇索引

（二级索引、辅助索引）

聚簇索引，只能在搜索条件是主键值时才发挥作用，因为B+树中的数据都是按照主键进行排序的，如果我们想以别的列作为搜索条件，那么需要创建非聚簇索引。

例如，以c2列作为搜索条件，那么需要使用c2列创建一棵B+树，如下所示：

这个B+树与聚簇索引有几处不同：

• 页内的记录是按照从c2列的大小顺序排成一个单向链表 。

• 页和页之间也是根据页中记录的c2列的大小顺序排成一个双向链表 。

• 非叶子节点存储的是记录的c2列+页号。

• 叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。

一张表可以有多个非聚簇索引：

6、说一下B+树中聚簇索引的查找（匹配）逻辑

7、说一下B+树中非聚簇索引的查找（匹配）逻辑

例如：根据c2列的值查找c2=4的记录，查找过程如下：

1. 根据根页面44定位到页42（因为2 ≤ 4 < 9）

2. 由于c2列没有唯一性约束，所以c2=4的记录可能分布在多个数据页中，又因为 2 ≤ 4 ≤ 4，所以确定实际存储用户记录的页在页34和页35中。

3. 在页34和35中定位到具体的记录。

4. 但是这个B+树的叶子节点只存储了c2和c1（主键）两个列，所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。

5. like 张%

8、平衡二叉树，红黑树，B树和B+树的区别是什么？都有哪些应用场景？

平衡二叉树

• 基础数据结构

• 左右平衡

• 高度差大于1会自旋

• 每个节点记录一个数据

平衡二叉树（AVL）

AVL树全称G.M. Adelson-Velsky和E.M. Landis，这是两个人的人名。

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。

具有以下特点：

• 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1

• 并且左右两个子树都是一棵平衡二叉树。

AVL的生成演示：https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL的问题

众所周知，IO操作的效率很低，在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐节点加载（一个节点一次IO）。如果我们利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。

为了提高查询效率，就需要 减少磁盘IO数 。为了减少磁盘IO的次数，就需要尽量降低树的高度 ，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。针对同样的数据，如果我们把二叉树改成 三叉树：

上面的例子中，我们将二叉树变成了三叉树，降低了树的高度。如果能够在一个节点中存放更多的数据，我们还可以进一步减少节点的数量，从而进一步降低树的高度。这就是多叉树。

普通树的问题

• 左子树全部为空，从形式上看，更像一个单链表，不能发挥BST的优势。

• 解决方案：平衡二叉树(AVL)

红黑树

• hashmap存储

• 两次旋转达到平衡

• 分为红黑节点

在这个棵严格的平台树上又进化为“红黑树”{是一个非严格的平衡树 左子树与右子树的高度差不能超过1}，红黑树的长子树只要不超过短子树的两倍即可！

当再次插入7的时候，这棵树就会发生旋转

B+ 树和 B 树的差异：

• B+树中非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大值（或最小）。

• B+树中非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而B树中， 非叶子节点既保存索引，也保存数据记录 。

• B+树中所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

9、一个b+树中大概能存放多少条索引记录？

• 真实环境中一个页存放的记录数量是非常大的（默认16KB），假设指针与键值忽略不计（或看做10个字节），数据占 1 kb 的空间：

• 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放 16 条记录。

• 如果B+树有2层，最多能存放 1600×16=25600 条记录。

• 如果B+树有3层，最多能存放 1600×1600×16=40960000 条记录。

• 如果存储千万级别的数据，只需要三层就够了

B+树的非叶子节点不存储用户记录，只存储目录记录，相对B树每个节点可以存储更多的记录，树的高度会更矮胖，IO次数也会更少。

10、使用B+树存储的索引crud执行效率如何？

c 新增

O(lognN)

N = 高度

11、什么是自适应哈希索引？

自适应哈希索引是Innodb引擎的一个特殊功能，当它注意到某些索引值被使用的非常频繁时，会在内存中基于B-Tree所有之上再创建一个哈希索引，这就让B-Tree索引也具有哈希索引的一些优点，比如快速哈希查找。这是一个完全自动的内部行为，用户无法控制或配置

使用命令

SHOW ENGINE INNODB STATUS \G ;

查看INSERT BUFFER AND ADAPTIVE HASH INDEX

12、什么是2-3树 2-3-4树？

多叉树（multiway tree）允许每个节点可以有更多的数据项和更多的子节点。2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少节点数量，增加分叉，减少树的高度，能对二叉树进行优化。

2-3树

下面2-3树就是一颗多叉树

2-3树具有如下特点：

• 2-3树的所有叶子节点都在同一层。

• 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。

• 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。

• 2-3树是由二节点和三节点构成的树。

• 对于三节点的子树的值大小仍然遵守 BST 二叉排序树的规则。

2-3-4树

13、为什么官方建议使用自增长主键作为索引？（说一下自增主键和字符串类型主键的区别和影响）

• 自增主键能够维持底层数据顺序写入

• 读取可以由b+树的二分查找定位

• 支持范围查找，范围数据自带顺序

字符串无法完成以上操作

14、使用int自增主键后 最大id是10，删除id 10和9，再添加一条记录，最后添加的id是几？删除后重启mysql然后添加一条记录最后id是几？

删除之后

• 如果重启，会从最大的id开始递增

• 如果没重启，会延续删除之前最大的id开始递增

15、索引的优缺点是什么？

优点

聚簇（主键）索引：

• 顺序读写

• 范围快速查找

• 范围查找自带顺序

非聚簇索引：

• 条件查询避免全表扫描scan

• 范围，排序，分组查询返回行id，排序分组后，再回表查询完整数据，有可能利用顺序读写

• 覆盖索引不需要回表操作

索引的代价

索引是个好东西，可不能乱建，它在空间和时间上都会有消耗：

• 空间上的代价

每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用 16KB 的存储空间，一棵很大的B+树由许多数据页组成，那就是很大的一片存储空间。

• 时间上的代价

每次对表中的数据进行 增、删、改 操作时，都需要去修改各个B+树索引。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位、页面分裂、页面回收等操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。

B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。

但B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。

16、使用索引一定能提升效率吗？

不一定

• 少量数据全表扫描也很快，可以直接获取到全量数据

• 唯一索引会影响插入速度，但建议使用

• 索引过多会影响更新，插入，删除数据速度

17、如果是大段文本内容，如何创建（优化）索引？

B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。

第一种方式是分表存储，然后创建索引

第二是使用es为大文本创建索引