学前提问:

这篇文章是介绍索引的,学之前带着问题,学完看看这些问题有没有被作者很好的解答:

  1. 索引是什么?
  2. 索引怎样使用?
  3. 索引的底层实现机制?
  4. 索引的使用注意事项?

索引是什么

维基百科:数据库索引是数据库管理系统中一个排序的数据结构,用来协助快速查询更新数据库表中的数据。

文章中作者的描述:简单来说,数索引的出现是为了提高数据查询效率,其作用类似书的目录

我get到的点:

  1. 索引是一种数据结构。【那么具体的数据结构实现是什么呢?,这个继续往下看】
  2. 索引的出现是为了提高查询和更新效率

索引的常见模型

索引的实现方式有很多种,既然索引是一种数据结构,那么也许和查询效率高的数据结构有关。果然这里作者介绍了三种常见,简单的数据结构,作为索引的数据的概念引入。

  • 哈希表
  • 有序数组
  • 搜索树

下面是对三种模型的简单分析:

哈希表:

  • 哈希表Key-Value 存储键值对的数据结构,根据键查找值。哈希模型的索引思路很简单,把值放在数组里,用哈希函数将 key 换算成一个确定的位置,把 vlue 放在数组的这个位置【key 存的是 value 所在数组的索引位置】

但是当多个 key 经过 hash 函数换算后的 value 相同时,就会引发冲突,针对这种情况的处理方法是:使用一个链表。

下面是一个说明的例子:假设现在维护了一个身份证信息和姓名的表,根据身份证号查找对应的名字,这时对应的哈希索引示意图如下

image-20200906001208724

可以看到,两个 value User4User2 哈希后的值都是 n,但是后面没有关系,这里数组上存储的是一个链表,这时根据 ID-Card-No2 这个key去找对应的name的步骤就是:

  • ID-Card-No2 先使用哈希函数算出值 n,然后根据 n 找到 一个链表,按顺序遍历 找到 User2

因为身份证号 ID-Card-No 并不是递增的,这样带来了好处弊端

好处:增加新的 User 速度很快,往后追加就可以。【这块我没理解往后追加是往哪里追加,数组还是链表?我觉得是数组,因为链表是哈希函数后相同哈希值存储在一个链表上】

弊端:无序导致范围查询效率很低,如果需要查找身份证号在[ID-Card-NoX,ID-Card-NoY] 之间的所有用户,则需要扫描全部的行。

结论:哈希表索引结构适用于只有等值查询的场景,例如:Memcached 以及其他 NoSQL 引擎。

有序数组

  • 有序数组:在等值查询范围查询场景中的性能都非常优秀。

上面的身份证号例子如果用有序数组实现的话,示意图如下:

image-20200906010443896

假设身份证号没有重复,这个数组按照身份证号递增的顺序进行保存。

这时候的需求是:查询 ID-Card-No2 对应的名字,使用**二分法**可以快速查到,时间复杂度 O(log(N))

并且这种索引结构支持范围查询,如果要查身份证号在 [ID-Card-X,ID-Card-Y] 区间的 User,可以先用**二分法找到 ID-Card-X如果不存在 ID-Card-X 就找到大于 ID-Card-X 的第一个 USer),然后向右遍历**,直到第一个大于 ID-Card-Y 的身份证号,退出循环

查询效率来看,有序数组是最好的数据结构。但是有序数组也存在硬伤插入数据数据效率太低,插入一个元素需要挪动后面所有的记录,成本很大。

有序数组的适用场景静态存储引擎,比如保存的是2017年某个城市的所有人口信息,这类不会再修改的数据。【数据量大,数据不会变动,这时使用有序数组可以获得最好的查询效率】

二叉树

  • 二叉搜索树经典的数据结构,特点是每个节点的左儿子小于父节点,父节点小于右儿子

使用二叉树实现上面的身份证查名字的示例图

如果查找 ID-Card-No2 的话,按照图中的搜索顺序是 UserA -> UserC -> UserF -> User2,时间复杂度是 O(log(N))。【这里作者介绍的太粗略了,只给了个结论,差评】

为了维持 O(log(N))查询复杂度,需要保持这棵树是平衡二叉树,所以更新的时间复杂度也是 O(log(N)),【同样的疑问,为什么? 需要自己去找答案】

不仅仅可以是二叉,也可以是多叉多叉树的每个节点有多个子节点,子节点之间的大小保证从左到右递增

二叉树的搜索效率最高,但是大多数据库存储却没有真正使用二叉树,原因在于索引不止存在于内存中,还需要写到磁盘里

如果有一棵 100 万个节点的平衡二叉树,树高20。一次查询可能需要访问 20 个数据块,在机械硬盘时代,从磁盘随机读一个数据库需要 10ms 左右的寻址时间,换算过来如果有一个 100 万行的,使用二叉树进行存储,单独访问一个行需要20个 10ms 的时间,查询效率很低。

所以数据库存储使用的是 b+ 树,而不是二叉树,因为二叉树的树高过高,每次查询需要访问过多的节点,访问节点需要访问数据块,而从磁盘随机读取数据块过于耗时。

所以提高效率的关键在于尽量少地读磁盘,少读盘就必须让查询过程访问尽量少地访问数据块。所以就不能使用二叉树,而要使用 N 叉树们这里的 N 取决于数据块的大小。

InnoDB 的一个整数字段索引为例,这个 N 差不多是 1200。 数高位4的时候,可以存 1200 的3次方个值,大约17亿。

考虑到树根的数据块总是在内存中,一个 10 亿行的表上一个整数字段的索引,查找一个值最多只需要访问 3 次磁盘。

树的第二层也有很大概率在内存中,访问磁盘的平均次数会更少。

N 叉树由于在读写上性能优秀,并且访问磁盘次数少。被广泛应用在数据库引擎中。

下面的专栏介绍了这几种树的特性,可以帮助理解:

平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了

小结一下:

  • 哈希表:适合等值查询场景,其更新效率高,但是范围查找效率低,只能遍历。
  • 有序数组查询效率最高,但是更新效率低,需要挪动更新节点之后的所有节点,适合做静态存储。
  • :二叉树在树结构中搜索效率最高,但是需要访问的节点最多,导致访问磁盘次数最多,查询耗时较长,所以数据库没有真正使用二叉树作为底层数据结构。

数据结构是不断发展的,跳表、LSM 树等数据结构也被用于引擎的设计中。【这里作者没有展开讲,只留下了个引子】

数据库底层存储的核心基于这些数据模型,每当遇到一个新的数据库,需要先关注它的数据模型,根据数据模型的不同就可以从理论上分析出这个数据库的适用场景。

【以上是作者用了大部分篇幅介绍的不同的数据结构以及其特点与适用场景,分析问题的时候经常会用到这些知识,并且都是硬核的知识,需要花时间和精力去学习,理解。】

InnoDB 索引模型

InnoDB

  • 索引选用的底层数据结构B+ 树
  • 存储方式索引组织表 —— 表根据主线顺序以索引的形式存放。

每个索引在 InnoDB 中对应一棵 B+ 树【这里作者的表达有歧义,应该是索引名称对应所有的索引记录,对应一棵 B+ 树,而不是单条记录就对应一棵 B+ 树。】

假设有一个主键列为 ID的表,表中有字段 kk 上存在索引

建表语句如下:

mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k)) engine=InnoDB;

表中 R1 ~ R5(ID,k)的值分别是(100,1)、(200,2)、(300,3)、(500,5) 和 (600,6) ,两棵树的示例示意图如下:

【首先,我看这个图没看懂,看看下面作者进行详细解释之后能不能看懂。】

根据叶子节点的内容,索引类型分为主键索引非主键索引。【但是看这个图我并没有看出哪个是主键哪个是非主键】

  • 主键索引的叶子节点存储整行数据InnoDB 中,主键索引也被称为**聚簇索引(clustered index)**

  • 非主键索引的叶子节点存储主键的值,在 InnoDB 中,非主键索引被称为**二级索引(secondary index)**。

那么问题来了,基于主键索引和基于普通索引查询之间的区别是什么?

  • 主键索引查询方式:select * from T where ID=500 , 查询时只需要搜索 ID(主键 ) 对应的这棵 B+ 树。
  • 普通索引查询: select * from T where k=5, 查询时需要先搜索 k 索引树,得到 ID的值为500,然后再去 ID 索引树搜索一次 ID 对应的 B+树,这个过程被称为回表。【普通索引需要先找对应的主键索引,这个操作称为回表,也就是多一次查询】

所以二级索引的查询语句比主键索引查询语句多一次回表操作,相当于要查2次,第一次得到主键,之后再用主键去查,而直接使用主键查询则可以一步到位,所以应尽量使用主键查询。

那么二级索引的优势呢?照这样说全用主键索引查就可以了。

索引维护

B+ 树的索引叶子节点是有序的,提升了查询效率,但是同时带来了增加新值时维护这个有序性的开销

举个例子:还是上面这个图,此时需要插入一个新的值,如果新的行 ID为700,则可以直接在 R5后面增加一条新纪录。但是如果 ID 是400,这时候就需要挪动 R3 之后的数据,空出位置。

还存在一种更糟的情况:R5 所在数据页已满,根据 B+ 树的算法,这时候需要申请新的数据页,挪动部分数据到新的数据页中,这个过程叫做页分裂。在这种情况下性能会受到更大的影响。

页分裂的出现不仅影响性,还影响了数据页的利用率,一个页能放下的数据现在放在两个页中,整体空间利用率降低大约 50%

小结:

页合并:相邻的两个页由于删除数据,利用率很低后,会将数据页合并,合并的过程是页分裂逆向过程

页分裂:新增数据所在的页已满时,需要申请新的数据页并挪动部分数据到新的数据页中的过程叫页分裂,会造成耗时并降低空间利用率

基于上面的知识探讨一个案例:

建表规范中可能有类似的描述,要求建表语句一定要有**自增主键**,事无绝对,下面要分析的是什么时候用自增主键,什么时候不用。

自增主键:自增列上定义的主键,对应的建表语句:NOT NULL PRIMARY KEY AUTO_INCREMENT

插入新纪录的时候可以不指定 ID 的值,系统会取当前 ID 最大值加 1 作为下条记录的 ID 值。

从性能角度出发

  • 自增主键的插入数据模式:符合前面提到的递增插入场景:每次插入一条新记录,都是追加操作,所以不会涉及挪动其他记录,也就不会触发叶子节点的分裂

  • 使用业务逻辑字段做主键:不容易保证有序插入,写数据时的成本较高

从存储空间利用率出发:

  • 每个非主键索引的叶子节点上都是主键的值,如果用身份证号做主键,每个二级索引的叶子节点占用约 20 个字节,如果用整形做主键,只需要 4 个字节,长整形(bigint)8个字节。

主键长度越小,普通索引的叶子节点也就越小,普通索引占用的空间越小。

性能存储两方面考虑,自增主键一般都是更好的选择。

但是事无绝对,也有适合用业务字段直接做主键的场景:

需求:

  1. 只有一个索引
  2. 该索引必须是唯一索引

这是典型的 Key-Value 场景,没有其他索引,也就不存在其他索引叶子节点大小的问题。这时候就可以考虑「尽量使用主键查询」原则,直接将这个索引设置为主键,可以避免每次查询都要搜索两棵树。

小结

KV 场景下,不存在其他索引,可以直接将业务字段设置为主键,省去一次查询且不需要担心其他索引叶子节点占用的字节更多。

小结

回顾学习之前的问题,做一个小结。

  • 索引是什么?
    • 索引是一种数据结构,定位类似字典的目录页,目的是为了增加查询效率
    • 索引可以

本章分析了数据库引擎可用的数据结构,然后主要介绍了 InnoDB 的 B+树结构,以及 InnoDB 使用 B+ 树的原因。

B+ 树的优点:访问磁盘的次数少,减少单词查询的访问磁盘耗时。

InnoDB 是索引组织表,一般情况下使用自增主键都是比较合适的选择,这样非主键索引的叶子节点占用空间最小,但是也有适合直接使用业务字段做主键的场景。

思考题:

针对上面的 InnoDBT,如果要重建索引 k ,可以向下面这样写

alter table T drop index k;
alter table T add index(k);

重建主键索引:

alter table T drop primary key;
alter table T add primary key(id);

针对上面重建索引的做法说出理解,并且指出是否不合适,以及怎样做更好。

思考:

普通索引的叶子节点存放的是主键索引,如果重建主键索引,意味着要更新所有的普通索引上保存的值,所以消耗比较大。

上节思考题:如何避免长事务对业务的影响

从开发端思考:

  • 确认是否使用 set autocommit = 0。这个确认工作可以在测试环境中做,打开 MySQLgeneral_log,然后跑一个业务逻辑,通过 genral_log 日志确认,如果使用的 ORM 框架修改了这个值,那么就需要使用 API 将这个值改为 1
  • 确认是否有不必要的只读事务。有的 ORM 框架会将任何的 SQL 语句都用 begin/commit 语句包裹,导致有的业务并不需要使用事务,比如一组 select 语句被加入了事务中,这种只读事务可以去掉。
  • 预估业务本身执行时间,设置 SET MAX_EXECUTION_TIME 控制每个语句执行的最长时间,避免出现单个语句执行太长时间。

从数据库端来看:

  • 监控 Information_schema.Innodb_trx 表,设置长事务阈值,超过就报警或者kill
  • Perconapt-kill 工具
  • 业务功能测试期间就输出所有 genral_log 分析日志提前发现问题
  • 如果使用的 MySQL 版本是 5.6 或更早的版本,将 innodb_undo_tablespace 设置为 2 (或更大值),如果真的出现大事务导致回滚段过大,这与设置后清理起来更方便。【为啥?】

精选留言:

  • 可以将每张表对应好几棵 B+树,树节点 key 值就是某行的主键value 是该行的其他数据新建索引就是新增一个 B+ 树,查询不走索引的话就是遍历 主 B+ 树
  • 如果一个表没有主键而存在普通索引,则 innodb 会默认创建一个 Rowid 做主键,这样普通索引查询才能完成回表

我的问题:

  • 1、介绍 InnoDB 索引组织结构的时候,引出了 R1~R5 ,但是却没有给出清晰的定义,到底是什么,是数据页,还是数据行?

image-20200921204542591

  • 2、

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住,曾是惊鸿照影来。