MySQL索引的数据结构

文章目录

• 一、索引的简介
• • 1、索引的概念
  • 2、索引的优点
  • 3、索引的缺点
• 二、索引的代价
• • 1、空间上的代价
  • 2、时间上的代价
• 三、InnoDB中索引的推演
• • 1、设计索引
  • 2、常见索引概念
  • • 2.1、聚簇索引
    • 2.2、二级索引（又叫辅助索引、非聚簇索引）
    • 2.3、联合索引
• 三、索引的数据结构
• • 1、全表遍历
  • 2、Hash结构
  • 3、二插搜索树
  • 4、AVL树
  • 5、 B树
  • 6、B+树
  • 7、R树
• 四、索引的适用和不适用场景
• • 1、适用场景
  • 2、不适用场景

1、索引的概念

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现 高级查找算法

2、索引的优点

• 类似大学图书馆建书目索引，提高数据检索的效率，降低数据库的IO成本 ，这也是创建索引最主要的原因。
• 通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。
• 在实现数据的参考完整性方面，可以 加速表和表之间的连接。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
• 在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时间 ，降低了CPU的消耗。

3、索引的缺点

• 创建索引和维护索引要 耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。
• 索引需要占 磁盘空间 ，除了数据表占数据空间之外，每一个索引还要占一定的物理空间， 存储在磁盘上 ，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
• 虽然索引大大提高了查询速度，同时却会 降低更新表的速度 。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。

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

1、空间上的代价

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

2、时间上的代价

每次对表中的数据进行 增、删、改 操作时，都需要去修改各个B+树索引。而且我们讲过，B+树每层节点都是按照索引列的值 从小到大的顺序排序 而组成了 双向链表 。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些 记录移位 ， 页面分裂 、 页面回收 等操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。

1、设计索引

可以联想操作系统中的页表机制，一层套一层（通过目录项找页，当目录项中过多时，我们会继续设置目录项去找目录项…），最后形成B+树的形式

1）以c1创建索引（因为c1是主键）

mysql> CREATE TABLE index_demo( ->   c1 INT, ->   c2 INT, ->   c3 CHAR(1), ->   PRIMARY KEY(c1) -> ) ROW_FORMAT = Compact;

2）数据库中一条记录的格式

• record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记录、 3 表示最大记录、 1 是目录项。
• next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁。
• 各个列的值 ：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3 。
• 其他信息 ：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

3）将记录放在数据页中

数据库中的数据在磁盘中是以数据页的形式进行存储的，每一页中的每一行叫做记录

页内的数据是按照主键值进行排序的，所以页内数据我们是可以通过二分法去查找的。

4）当页过多时，需要为页设置目录项

5）当目录项过多时，我们需要为目录项设置目录项

6）最后形成B+树的形式

一个B+树的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记录的那层为第 0层，之后依次往上加。之前我们做了一个非常极端的假设：存放用户记录的页最多存放3条记录 ，存放目录项记录的页 最多存放4条记录 。其实真实环境中一个页存放的记录数量是非常大的（MySQL中一页的大小为16KB），假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录，所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录 ，那么：

• 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放 100 条记录。
• 如果B+树有2层，最多能存放 1000×100=10,0000 条记录。
• 如果B+树有3层，最多能存放 1000×1000×100=1,0000,0000 条记录。
• 如果B+树有4层，最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。相当多的记录！！！

因此，面试中问，为什么MySQL的B+树最多只有四层？
因为四层就已经能够存储相当量的数据了，足够我们使用，毕竟四层可以存储100000000000 条记录了。

那怎么去查找我们所需要的的记录了？
通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的 Page Directory（页目录），所以在页面内也可以通过 二分法 实现快速定位记录

2、常见索引概念

2.1、聚簇索引

特点

上面举的例子是基于主键进行排序的，所以是聚簇索引！

• 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
  • 页内 的记录是按照主键的大小顺序排成一个 单向链表。
  • 各个存放 用户记录的页 也是根据页中用户记录的主键大小顺序排成一个 双向链表 。
  • 存放目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个 双向链表。
• B+树的 叶子节点 存储的是完整的用户记录。
  所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）

优点

• 数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
• 聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
• 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以 节省了大量的io操作 。

缺点

• 插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
• 更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新
• 二级索引访问需要两次索引查找 ，第一次找到主键值，第二次根据主键值找到行数据

2.2、二级索引（又叫辅助索引、非聚簇索引）

二级索引我们并不是将主键作为索引，而是用非主键进行索引。每一行的记录包括非主键的索引和主键。

因此我们利用二级索引去查找某个完整的记录，需要两步操作，第一步，通过二级索引去查找主键，第二步，通过聚簇索引去查找记录。
这就是回表操作，所以查找一条记录我们需要查找两棵B+索引树！

面试问题，为什么需要一次回表操作了？直接把完整的用户记录放到叶子节点不OK吗？
因为在数据库中不会只设置一个二级索引，如果每个二级索引的叶子结点都放置完整的用户数据（每个用户的数据可能有几百万个），会极大的加大存储空间的开销

2.3、联合索引

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照 c2和c3列 的大小进行排序，这个包含两层含义：

• 先把各个记录和页按照c2列进行排序。
• 在记录的c2列相同的情况下，采用c3列进行排序

注意一点，以c2和c3列的大小为排序规则建立的B+树称为 联合索引 ，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：

• 建立 联合索引 只会建立如上图一样的1棵B+树。
• 为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。

1、全表遍历

复杂度是O(n)的，效率很差

2、Hash结构

Hash结构的效率是很高的，时间复杂度可以为O（1）

那为什么Hash结构的效率这么搞，那为什么索引的数据结构设计成树形了？有四点原因

Hash索引适用存储引擎如表所示：

虽然在InnoDB存储引擎中，不支持Hash索引，但是却提供了自适应Hash索引(Adaptive Hash Index)。

那什么情况下使用自适应Hash索引了？

如果某个数据经常被访问，当满足一定条件的时候，就会将这个数据页的地址存放到hash表中，这样在下次查询的时候，就可以找到这个页面所在的位置。这样B+树也具备了Hash索引的优点。

采用自适应 Hash 索引目的是方便根据 SQL 的查询条件加速定位到叶子节点，特别是当 B+ 树比较深的时候，通过自适应 Hash 索引可以明显提高数据的检索效率。

我们可以通过innodb_adaptive_hash_index变量来查看是否开启了自适应 Hash，比如：

show variables like '%adaptive_hash_index';

3、二插搜索树

二插搜索树在某种情况下，时间复杂度会变成O(n)

为了提高查询效率，就需要 减少磁盘IO数 。为了减少磁盘IO的次数，就需要尽量 降低树的高度 ，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。

4、AVL树

5、 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]，且关键字按照升序排序，即 Key[i]
…,P[k]，其中 P[1] 指向关键字小于 Key[1] 的子树，P[i] 指向关键字属于 (Key[i-1], Key[i]) 的子树，P[k]>指向关键字大于 Key[k-1] 的子树。
（4）所有叶子节点位于同一层。

上面那张图所表示的 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次数足够少，就可以提高查询性能

6、B+树

B+树和B树的差异

• B+树有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数+1。
• B+树中，非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
• B+树中，非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中， 非叶子节点既保存索引，也保存数据记录 。
• 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

B+树就比B树好吗？

B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。但B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。

3 、思考题：为了减少IO，索引树会一次性加载吗？

不会，因为索引会占用空间，大量的索引可能会超出1g多的大小，所以不会一次性加载

思考题：B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO

储存能力很强，倘若一开始的根页可以存放100条数据条目，那如果页目录可以存放1000条，那二级存放的量就1001000，三级就是10010001000,4级就是100100010001000，那为什么最多只需要加载最大3次呢，因为根页的数据在一开始已经加载了所有无需加载，那么就算最大加载4级，那也就需要加载最大3次

思考题：为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？

因为B+树查询更为稳定，且适合范围的快速查找

思考题：Hash 索引与 B+ 树索引的区别

HASH索引的范围查找效率比B+树索引效率低很多，且不支持联合索引

思考题：Hash 索引与 B+ 树索引是在建索引的时候手动指定的吗？

不是的，是一开始我们创建表的时候，每次插入数据，他背后都会去维护对应索引，如果又新加的二级索引才会再创建索引

7、R树

R-Tree在MySQL很少使用，仅支持 geometry数据类型 ，支持该类型的存储引擎只有myisam、bdb、innodb、ndb、archive几种。

举个R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。如果没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌、百度地图这种超大数据库中，这种方法便必定不可行了。R树就很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树 。相对于B-Tree，R-Tree的优势在于范围查找

1、适用场景

• 主键自动建立唯一索引
• 频繁作为查询的条件的字段应该创建索引
• 查询中与其他表关联的字段
• 频繁更新的字段不适合创建索引
• 查询中排序的字段，排序字段若通过索引去访问将大大提高排序的速度
• 查询中统计或者分组字段

2、不适用场景

• Where条件里用不到的字段不创建索引
• 表记录太少
• 经常增删改的表
• 数据重复且分布平均的表字段

来源地址：https://blog.csdn.net/qq_38327769/article/details/124244178