本文导读
本篇文章博主对索引做了一个较为初步地概述,主要有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+树索引由根节点、非叶节点和叶节点组成,其中叶节点存储所有排序的数据。
所有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索引树上的话。可以直接提供查询结果而不返回表,这个查询,索引覆盖了我们的查询需求,我们称之为覆盖索引。
由于覆盖索引可以减少树搜索的数量并显著提高查询性能,因此使用覆盖索引是一种常见的性能优化方法。
如果现在有高频请求,可以在这个高频请求上使用覆盖率索引,无需返回表检查整行记录,并减少语句执行时间。当然,索引字段的维护总是有代价的。因此,在建立冗余索引以支持覆盖率索引时,有必要考虑权衡。
总结
本篇文章博主对索引做了一个较为初步地概述,主要有2种主要的索引的数据结构b+tree和hash的数据结构,b+树的覆盖索引和回表进行分析,并对b+树存放记录、如何优化B+树索引的插入性能进行分析。