【MySQL】深入理解MySQL索引原理(MySQL专栏启动)

本文导读

本篇文章博主对索引做了一个较为初步地概述,主要有2种主要的索引的数据结构b+tree和hash的数据结构,b+树的覆盖索引和回表进行分析,并对b+树存放记录、如何优化B+树索引的插入性能进行分析。

一、 MySQL索引数据结构模型

众所周知,数据库查询是数据库的核心功能,索引是加速查询的重要技术手段。

MySQL对索引的官方定义是存储引擎用来快速查找记录的数据结构。一般来说,索引类似于图书目录。它以增加写入和存储空间为代价,提高了数据库表上数据检索操作的速度。您可以根据其中记录的页码快速找到所需内容。

索引是物理数据页,数据库页面大小决定了页面可以存储多少索引行,以及存储指定大小的索引需要多少页面。索引数据结构选择的本质是根据当前数据读写的硬件环境,选择一个优秀的数据结构进行数据存储和遍历。

索引可以加快检索速度,但也可以降低插入、删除和更新索引列的速度。索引同时维护需要一定成本

数据库中的大多数索引都是通过B+Tree实现的。当然,还涉及其他数据结构,索引涉及的理论知识包括哈希表和B+树

1、B+Tree(B+树)索引

B+ 树索引是数据库中最常见的索引数据结构,为什么关系数据库热衷于支持B+树索引?

与二叉树、散列索引、红黑树和SkipList相比,在基于磁盘的海量数据存储效率方面远不如B+树索引,因此,上述数据结构通常仅用于内存对象。

对于基于磁盘的数据排序和存储,最有效的仍然是B+树索引。B+树索引的特点是基于磁盘的平衡树,树通常为3到4层,可以存储数千万到数亿的排序数据。树短意味着访问效率高。从数千万或数亿数据中查询一条数据只需要3或4个I/O。

因为SSD(固态硬盘)每秒可以执行至少10000个I/O,所以查询一段数据只需要0.003到0.004秒,即使数据都在磁盘上。此外,由于B+树较短,在排序时,它只需要比较3到4次,就能找到需要插入数据的位置。分拣效率非常好。

B+树索引由根节点、非叶节点和叶节点组成,其中叶节点存储所有排序的数据。

【MySQL】深入理解MySQL索引原理(MySQL专栏启动)

所有B+树都从高度为1开始,然后根据数据的插入慢慢增加树的高度。索引用于对记录进行排序,高度为1的B+树索引中存储的记录已排序,如果想在叶节点中进行查询,您可以只通过二进制搜索快速找到数据。

当一个页面(16K)无法存储如此多的数据,因此B+树将分裂。B+树的高度将变为2。当B+树高度大于或等于2时,根节点和中间节点存储由(索引键和指针)组成的索引键对。索引键是已排序的列,指针是指向下一层的地址,这在MySQL的InnoDB存储引擎中占用了6个字节。

2、Hash 索引

哈希表是数据库中哈希索引的基础。它是根据键值<key,value>存储数据的结构。

使用哈希函数计算桶或槽的索引列的数组。实际的存储是根据哈希函数将 key 转换为确定的存储位置,并将值存储在数组位置。访问时,只需要输入要搜索的 key ,然后就可以通过哈希函数计算确定的存储位置并读取数据。

在 MySQL 中主要是分为三种哈希索引:

Memory 存储引擎原生支持的 Hash 索引

InnoDB 自适应哈希索引

NDB 集群的哈希索引

3、InnoDB 自适应哈希索引

InnoDB 自适应哈希索引旨在提高查询效率。

InnoDB 存储引擎将监视表上每个索引页的查询。当 InnoDB 注意到某些索引值被非常频繁地访问时,将基于B+树索引在内存中创建另一个哈希索引,从而使内存中的B+树具有哈希索引的功能,即可以快速访问具有固定值的频繁访问的索引页。

为什么要为B+树索引页创建自适应哈希索引?

这是因为B+树索引的查询效率取决于B+树的高度,在数据库中B+树的高度通常为3到4层,因此需要执行3到4个查询才能访问数据。

哈希索引可以在单个搜索中定位数据(没有哈希冲突),并且哈希索引在其等效查询场景中的查询效率优于B+树。

自适应散列索引的建立使 InnoDB 存储引擎能够根据索引页访问的频率自动为热点页创建散列索引,以加快访问速度。

二、B+ 树索引理论上每层最多能存放多少行记录

根节点最多可以存储键值对 = 16K/键值对大小(8+6)≈ 1100

叶节点存储的最大记录数 = 16K/每条记录的大小 ≈ 32

总记录数 = 根节点最多可以存储以下多个键值对 * 叶节点最多可以保存以下多个键值对

所以二层是1100*32 = 35200

树高为3的B+树索引中可以存储的最大记录数为:总记录数=1100(根节点)*1100(中间节点)*32 = 38720000

树高为4的B+树索引中可以存储的最大记录数为:总记录数=1100(根节点)*1100(中间节点)*1100(根节点)*32 = 42592000000

不过,在真实环境中,每个页利用率并没有这么高,还会存在一些碎片的情况,我们假设每个页的使用率为60%。十亿级别的数据量查询也只需要4次IO。

三、优化 B+ 树索引的插入性能

1、索引维护原理

为了维持索引的顺序,在插入、删除时需要维护B+树。

如果是插入,一般有三种情况,

1、只需要在页记录之后插入一条新记录。

2、需要按逻辑移动以下数据以腾出空间

3、需要申请一个新的数据页,然后将一些数据移到过去(分页)在这种情况下,性能自然会受到影响。

除性能外,页拆分还影响数据页的利用率。原来放在一个页上的数据现在被分成两个页,总体空间利用率降低了约50%。当然,有分裂的地方就有合并。

当由于删除数据而导致两个相邻页的使用率较低时,数据页将被合并。合并过程可视为拆分过程的反向过程。

2、每张表尽量使用自增ID主键

自增加主键的数据插入模式,每次插入新记录时,都是追加操作,它不涉及移动其他记录,也不触发叶节点的拆分,这样,可以避免最后两种影响性能的情况。

要确保以业务逻辑为主键的字段的有序插入并不容易,因此写入数据的成本相对较高。如果将业务逻辑的字段用作主键,通常不容易确保有序插入,因此写入数据的成本相对较高。

主键长度越小,索引的叶节点就越小,而索引占用的空间就越小。因此,从性能和存储空间的角度来看,自动增长的主键往往是一个更合理的选择。

四、B+树 覆盖索引与回表

回到主键索引树搜索过程,称为回表,查询结果所需的数据仅在主键索引上可用,必须将其返回到表中获取数据。

如果要执行的语句  select ID from T where,只需要查询ID值,并且ID值已经在k索引树上的话。可以直接提供查询结果而不返回表,这个查询,索引覆盖了我们的查询需求,我们称之为覆盖索引。

由于覆盖索引可以减少树搜索的数量并显著提高查询性能,因此使用覆盖索引是一种常见的性能优化方法。

如果现在有高频请求,可以在这个高频请求上使用覆盖率索引,无需返回表检查整行记录,并减少语句执行时间。当然,索引字段的维护总是有代价的。因此,在建立冗余索引以支持覆盖率索引时,有必要考虑权衡。

总结

发表评论

相关文章