索引的数据结构

  • 索引是存储引擎用于快速查找数据的一种数据结构。可以理解为”排好序的快速查找数据结构“，满足特定算法。这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现”高级查找算法“。
  • 进行数据查找时，首先看查询条件是否命中某条索引，是的话就通过索引查找数据；否则就需要进行全表扫描，直到查询到符合条件的记录。
  • 目的就是为了减少磁盘IO次数，加快查询效率。
  • 索引是在存储引擎中实现的。所以每种存储引擎的索引不一定完全相同

索引的优缺点

优点

  1. 提高数据检索的效率，降低数据库的IO成本 ，这也是创建索引最主要的原因。
  2. 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性。
  3. 在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时间 ，降低了CPU的消耗。

缺点

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

InnoDB中的索引

  • 对于查询语句select 字段 from 表名 where 条件 = xxx;

无索引场景一：单数据页查找

  • 如果数据量比较少，所有的数据都在同一个数据页（16k）中，在查找的时候根据条件可以分为：

    1. 以主键为搜索条件（假定主键自增），可以采用二分法进行查找
    2. 非主键为搜索条件，只能从最小记录开始遍历查找，由于记录在磁盘中并不是物理连续的，而是逻辑连续的，其实查找的效率并不高。

无索引场景二：多数据页查找

  1. 首先需要找到数据所在的页，同样，页也并不是物理连续的，而是通过链表进行连接，形成逻辑连续。所以只能从第一页沿着双向链表一直往下找。
  2. 然后根据单页的规则进行查找。同时，将页数据加载进内存更加耗费时间

数据模型

  • 对于无索引查找，导致的效率低下的问题，可以采用索引进行解决。那么如何设计索引呢？

  • 基本模型

    1. CREATE TABLE index_demo ( 
    2. c1 INT, 
    3. c2 INT, 
    4. c3 CHAR ( 1 ),
    5. PRIMARY KEY ( c1 ) ) 
    6. ROW_FORMAT = Compact;


ROW_FORMAT：行格式，表中每一行记录的格式，除了字段的值之外还会有额外信息

示意图如下

索引的数据结构 - 图1

  • record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记录、 3 表示最大记录、 1 暂时还没用过，下面讲。

  • next_record ：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁。

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

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


行数据在页中的示意图

索引的数据结构 - 图2

简单的索引设计方案

  • 插入数据：INSERT INTO index_demo VALUES(1,4,'u'),(3,9,'d'),(5,3,'y');

  • 那么数据在页中的展示如下

    大小按照主键进行判断

索引的数据结构 - 图3

  • 接着插入一条数据：INSERT INTO index_demo VALUES(4,4,'a');

    假设每个页最多存放3条数据，索引新的记录需要分配一个新的页进行存储

索引的数据结构 - 图4

但是这并不合理，页28主键4并没有比页10主键5大，所以需要进行记录移动：也即将主键4和主键4进行页间交换

索引的数据结构 - 图5

在对页中数据进行增删改的时候，必须通过一些诸如记录移动的操作来始终保持下一个数据页中的最小值必须大于上一个页中的最大值。这个过程称为页分裂

  • 插入更多数据后，可能页面之间的示意图如下

    索引的数据结构 - 图6

存在的问题：比如我们需要查找主键100的行数据，还是需要从最小的页开始遍历。当页足够多的时候，效率还是比较低。

  • 给所有的页建立一个目录项

    由于页是不连续的，想要快速定位到数据所在页，可以给数据页建立一个目录项，目录项是连续的

key：当前页最小的值

page_no：页号

索引的数据结构 - 图7

比如我们要查找主键20，首先1<5<20，所以页10直接跳过；5<12<20，所以页28直接跳过；12<20<209，所以数据在页9中，然后将页9加载进内存开始查找。

InnoDB中的索引

目录项记录的页

  • 上述索引方案存在的问题：当目录项很多的时候，连续空间造成的压力比较大；同时，对于目录项的增删改也需要耗费时间，比如，中间新增一个目录项，后面的目录项全都需要后移一个。

  • 所以我们可以灵活管理所有目录项，参考数据页的存储方式，目录项示意图如下

    索引的数据结构 - 图8

和数据页的不同点：

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

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

  • 了解：记录头信息里还有一个叫 min_rec_mask 的属性，只有在存储 目录项记录 的页中的主键值最小的 目录项记录 的 min_rec_mask 值为 1 ，其他别的记录的 min_rec_mask 值都是 0 。

相同点：两者用的是一样的数据页，都会为主键值生成 Page Directory （页目录），从而在按照主键值进行查找时可以使用 二分法 来加快查询速度。

查找主键20步骤如下：

  1. 加载目录页进内存，12<20<209，所以记录在页9
  2. 加载页9进内存，查找主键20的记录

多个目录项

  • 当数据页增多，同时需要扩展目录项的时候

    索引的数据结构 - 图9

但数据量越来越多，就会导致跟之前一样的问题。

需要遍历目录项找到数据所在的页信息

目录项的目录项

  • 继续向上进行抽取

    索引的数据结构 - 图10

索引的数据结构 - 图11

其实整个过程看下来，就是在尽量减少磁盘IO

B+树

  • 不论是存放用户记录的数据页，还是存放目录项记录的数据页，都存放在B+树结构中，所以我们也称这些数据页为节点

  • 存放用户记录的节点都在B+树的地段，称为叶子结点

  • 其余用来存放目录项的节点称为非叶子节点

  • 最上层的存放目录项的节点称为根节点

  • 问题：为什么B+树一般不超过4层？

    • 对于精确查找来说，层数越低，IO次数越少（精确查找的时候，对于数据项，只需要一次IO。范围查找对于数据项需要多次）
    • 每个数据页大小16k，int类型主键大小4字节，bigint8字节，指针大小4字节为例。一个页中大概存储16K/(8+8)=1000个键值（bigint为例）。4层存放的记录个数103×103=1000亿

索引概念

聚簇索引

  • 聚簇索引并不是一种单独的索引类型，而是一种数据存储方式（磁盘上存储的形式就是B+树的数据结构）。也即索引即数据，数据即索引

  • 特点：

    1. 使用记录主键值的大小进行记录和页的排序

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

      • 各个存放 用户记录的页 也是根据页中用户记录的主键大小顺序排成一个 双向链表 。

      • 存放 目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个 双向链表 。

    2. B+树的叶子结点存储的是完整的用户记录（存储了所有列的值，包括隐藏列）

具有这两种特性的B+树称为聚簇索引。

  • 优点：

    • 数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引（不包含数据的索引）更快

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

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

  • 缺点：

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

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

    • 二级索引访问需要两次索引查找 ，第一次找到主键值，第二次根据主键值找到行数据

  • 限制：

    • InnoDB支持，MyISAM不支持
    • 由于数据物理存储排序方式只能有一种，所以每个MySQL的表只能有一个聚簇索引，一般是该表的主键
    • 如果没有定义主键，InnoDB会选择非空的唯一索引代替。如果也不存在，InnoDB会隐式创建一个主键作为聚簇索引
    • 为了充分利用聚簇索引的聚簇特性，所以InnoDB一般选用有序的顺序id作为主键，而不建议使用无序的id，比如uuid,md5等等无法保证数据的顺序增长

二级索引

  • 也称为辅助索引、非聚簇索引，可以有多个。而聚簇索引只能有一个

  • 聚簇索引智能在条件为主键的时候生效 ，而对于非主键值，可以多建立几个B+树

    索引的数据结构 - 图12

只不过不同的是，叶子结点不再是完整的数据

叶子结点中，分别是排好序的字段值以及这条记录对应的主键值

当查找到条件对应的主键值之后，再根据主键值采用聚簇索引去找到数据项，这个过程就叫做回表，也即根据此索引查找数据需要两棵B+树。

  • InnoDB中索引分布

    1个聚簇索引，多个非聚簇索引

索引的数据结构 - 图13

  • 小结

    • 聚簇索引的叶子结点是完整的数据项，非聚簇索引的叶子结点存储的是数据的位置。
    • 非聚簇索引不会影响数据表的物理存储顺序
    • 一个表只能有一个聚簇索引，可以有多个非聚簇索引。
    • 聚簇索引查询效率高，对数据的插入删除以及更新会比非聚簇索引效率低。因为影响不到非聚簇索引（除非修改主键）。

联合索引

  • 以多个列的大小作为排序规则，也就是同时为多个列建立索引。

  • 比如想建立联合索引，对应的列为c2,c3。那么按照c2，c3进行排序就是：

    • 先把各个记录和页按照c2列进行排序。

    • 在记录的c2列相同的情况下，采用c3列进行排序

  • 建立的示意图如下

    索引的数据结构 - 图14

叶子结点从上倒下分别为：c2,c3,主键

c2按照从小到大排好序，同时c2相等的话，再根据c3从小到大排序

InnoDB的B+树索引注意事项

  1. 聚簇索引根节点一直不动

    • 建表的时候（InnoDB存储引擎）默认会创建一个聚簇索引，同时创建一个根节点页面，根节点存储数据项
    • 当数据项根节点页面存储满了的时候，新建一个页面，将根节点的数据复制过去，根节点存储目录项，同时对新的页面进行页分裂，得到新的页，数据存储进新的数据页
    • 当目录项根节点再次存满的时候，新建一个页面，将根节点中的目录项复制进去，根节点成为存储目录的目录项
    • 同时，根节点一般常驻内存，IO次数只需要层数-1
  2. 非聚簇索引非叶子节点记录的唯一性

    上面描述的非聚簇索引是存在问题的：上面描述的目录项存储的是索引列+页号

索引的数据结构 - 图15

当我们新插入一行数据，索引列为1，那么由于页3中存在多个索引列为1的页（不包括页号），就导致数据不知道存储到哪个页面

所以需要保证在B+树的同一层非叶子节点的目录项记录除了页号字段之外是唯一的。

也即将主键值也添加到非叶子节点的

索引的数据结构 - 图16

  1. 一个页面至少可以存放两条记录以形成二叉树

MyISAM中的索引

  • MyISAM数据存储在.myd文件中，索引存储在.myi文件中

  • MyISAM索引同样是一棵B+树，data域保存的是地址

  • MyISAM不存在聚簇索引，只存在非聚簇索引

  • MyISAM数据文件以及索引文件

    插入数据的时候，数据文件按照插入的顺序进行存储。数据文件并不会划分为多个，而是一直往一个数据文件记性存储

对于主键来说，MyISAM会单独为表的主键创建一个索引，只不过在索引的叶子结点中存储的不是完整的用户记录。而是主键值+数据记录地址的组合（.myd中的位置）

索引的数据结构 - 图17

对于非主键来说，大体类似，只不过需要我们自己创建。

索引的数据结构 - 图18

InnoDB和MyISAM索引对比

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

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

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

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

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

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

  • 了解索引结构之后，可以得到实践中的建议：

    • 在InnoDB中，创建的主键最好是顺序增长的，同时主键不应该过长，因为每一个节点都会存储主键

      索引的数据结构 - 图19

索引的代价

  1. 空间上：每一个索引都是一个B+树，树的每一个节点都是一个数据页，每个大小是16K，当数据页很多，那就是一大片存储空间
  2. 时间上：每次增删改的时候，都需要维护索引。尤其是当增删改破坏了索引列的顺序的时候，存储引擎还需要进行记录移位，页面分裂，页面回收等操作。如果建立了很多索引，每个B+ 树都需要这么操作的话，时间上总会有影响。

MySQL索引数据结构

  • 参考的角度就是：磁盘IO次数，由于索引文件可能较大，全部加载进内存并不现实，所以需要逐一加载进内存

Hash结构的索引

  • Hash结构

    索引的数据结构 - 图20

  • Hash作为索引存在的问题

    1. Hash索引只能够满足等于，不等于，IN查询。如果进行范围查询，效率会退化为O(n)，因为不是有序的
    2. ORDER BY，还需要重新排序
    3. 联合索引是将多个键合并后计算的，不支持使用部分索引
    4. Hash冲突的时候，效率降低。所以Hash索引通常不会用在重复值多的列上。

  • 支持Hash索引的存储引擎：Memory存储引擎

  • InnoDB自适应Hash索引

    • 如果某个数据经常被访问，当满足一定条件的时候，会将这个数据页的地址存放在Hash表中。下次再查询的时候，就可以直接找到这个页面所在的位置

      索引的数据结构 - 图21

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

show variables like '%adaptive_hash_index';：MySQL8.0.26默认开始

B-Tree数据结构

  • B树的结构

    索引的数据结构 - 图22

非叶子节点也存储数据

B+ Tree数据结构

  • 与B树的区别：非叶子结点不存储数据

  • B+树相对B树的优势：

    1. B+树查询效率更稳定，磁盘IO次数就是树高。而B树可能在根节点就可以找到数据，也可能要到叶子结点才能找到数据
    2. B+树查询效率更高，通常情况下，树高比B树更低。因为同样的磁盘大小，B+树存储的结点数据更多
    3. 在范围查询上，B+树效率更高。因为所有的数据都在叶子结点上，同时是有序的。