1.Base基础/3.Icon图标/操作/search备份
1.Base基础/3.Icon图标/操作/search备份
EN
数据库性能优化必读,AntDB-M数据库的哈希索引设计
News-2023-06-26
亚信安慧科技

数据库加快访问速度的关键技术之一就是索引,索引的设计及使用方式极大程度上影响了数据库的性能。AntDB-M支持Hash、BTree两种索引类型。本文主要讲解Hash索引的相关设计,并给出一些使用建议。

1. 相关概念

l

用于定位索引记录的容器,容器中的每个元素记录的是表记录的唯一编号,元素为空说明当前索引位置没有表记录。

l桶大小

一个桶中可以直接存储的记录唯一编号个数。

l桶下标

桶下标由索引列经过Hash计算后得到的Hash值与桶大小取模得到。

l索引记录链表

由于Hash冲突的存在,不同表记录经过Hash计算得到的桶下标可能相同,对于相同桶下标的索引记录都存放在一个双向链表中,即索引记录链表,桶上元素的就是索引记录链表头。

2. 内存结构

AntDB-M的Hash索引内存结构设计非常简洁、高效。每个Hash索引都有两部分组成:桶、索引记录链表。

 

l

桶为一个一维数组,数组中的每个元素都是表记录的唯一编号索引记录的唯一编号记录唯一编号相同


1

l索引记录链表

AntDB-M索引记录链表用于记录具有相同hash值的索引记录内存结构是一个三层结构:1)一级地址;2)二级地址;3)链表节点; 该结构的组织形式与表数据的组织形式类似(参考“AntDB-M 设计之内存结构”),可以通过记录的唯一编号快速定位到链表中的记录。

索引记录链表的节点有三部分组成:前一个记录编号、后一个记录编号、事务唯一索引 记录的记录编号链表结点记录编号

2索引记录链表

上文可以看出Hash索引整个结构中仅仅涉及记录编号与事务信息结构非常轻便按需扩展内存占用过高的内存

1. 索引处理

3.1 持久化

AntDB-M索引包括两部分数据:索引元数据、索引记录。在做数据的持久化时,只会对索引元数据做持久化。

3.2 初始化

AntDB-M数据库服务启动时,首先加载表数据记录,然后加载索引元数据,最后根据索引元数据在内存中初始化索引记录。

3.3 插入索引记录

表插入一条记录时,会先插入表记录,再插入索引记录。记录添加索引链表头部,提高插入速度。

l普通索引


3普通索引插入

对于普通索引因为不需要判断记录的唯一性所以并发插入不会相互影响,可以直接插入。新插入的索引记录是立即生效的,即其他事务查询时可以立即访问,但是表记录的可见性由表记录上的事务信息以及锁来控制。在事务提交时,普通索引不需要任何处理。事务回滚时,将索引记录本身从索引记录链表中删除。

 

l唯一索引


4唯一索引插入

对于唯一索引需要检测是否存在唯一键冲突当相同桶下标的索引记录链表中已经存在相同记录,并且事务还未提交(索引记录事务字段有值),则阻塞等待其他事务提交或者回滚,以检测唯一键冲突。事务提交,清除索引记录事务信息。事务回滚删除索引记录。事务提交、回滚都会通知正在阻塞等待的事务。

 

3.4 索引查询

哈希索引查询根据索引计算哈希哈希大小取模获取下标然后获取遍历下标下的索引记录列表获取匹配记录的记录编号编号放入当前事务分配的查询上下中,后续查询遍历使用索引记录数据记录拥有相同的记录编号,根据记录编号可以立即定位到数据记录整个过程主要开销哈希值的计算索引记录比较性能非常高。

3.5 删除索引记录


5-普通索引删除


6-唯一索引删除

表删除一条记录时,先删除表数据记录标记删除标识更新事务信息然后更新唯一索引记录上的事务为当前事务由于普通索引并没有事务信息因此不会任何操作更新索引记录上的事务是为了数据记录唯一性多事务并发时的冲突检测。因为当前事务已经获取了记录上的互斥锁,所以更新索引记录影响索引记录一致性,可以直接更新

事务提交时,索引记录并不立即删除,在查找时通过索引还是会找到索引记录。表记录的的可见性仍然有表记录上的事务信息、锁信息来控制MVCC后续会有单独的清理线程数据记录没有事务访问数据记录索引记录进行实际删除

事务回滚时,只需要唯一索引清除索引记录上的事务信息。

如果是唯一索引,事务提交、回滚都会通知正在阻塞等待的事务。

3.6 更新索引项

表记录的更新,只有涉及到索引列更新时,才会更新索引。涉及索引更新时,表记录的修改会转换为先删除旧记录,后插入新记录的方式。对于索引的操作也同样转换为上文的插入索引项、删除索引项。 事务的提交、回滚也同上文的插入索引项、删除索引项。

3.7 节点链表扩展

索引节点链表空间大小(记录个数)与表记录空间大小保持一致。 当表中新记录超出表空间大小,需要对表空间扩展时,同时对索引节点链表进行扩展。

3.8 桶重建(rehash)

在创建索引时,索引桶大小初始值可以由索引属性block_size来指定,未指定则以表当前记录数为准,最小值为100000。 定时检测(默认5分钟,可配置)表记录数是否超过桶的大小,超过了便对桶进行扩展,并重建Hash索引。

l新桶大小

新桶大小为比当前桶大小大的最小素数。

l桶访问锁

对于每个线程,在初次访问索引时都会分配一个桶访问节点,该节点上设置了当前的桶地址,以及一把互斥锁。在线程开始访问索引时,先申请访问节点上的锁,访问结束释放锁。通过该锁确保索引访问过程中,桶资源不会因为rehash被释放。

l异步重建

桶重建是一个异步过程,重建桶过程中,并不影响索引的查询以及更新。该过程通过记录当前迁移位置来影响访问旧桶,还是新桶。当数据迁移完毕,并且没有对旧桶的访问时(没有线程持有该桶的桶访问锁),对旧桶资源进行释放。

3.9 索引与锁

为了避免过多的锁占用系统过多资源,以及保持较高的并发度,AntDB-M数据库的每个Hash索引都分配有131个锁,通过桶下标与131取模来获取当前索引记录的锁。在访问索引(查询或者修改)过程中都会先加锁。

 

1. 索引特性

4.1 前缀索引

前缀索引是指适用指定列,或者指定列的指定前缀长度做为索引。

这种特性适用于以下两种情况

1. 索引列数据过长

2. 索引列部分数据适用于特定业务查询的场景。

AntDB-M还可以指定每列的前缀长度,而不仅仅是最后一列的前缀长度,这就业务提供了非常灵活的索引能力方便客户实现高效响应速度更快的业务落地

4.2 数据分布

对于每个Hash索引,都会统计当前位置下Hash值相同记录个数。

该统计值主要用来判断当前数据是否存在较大的Hash冲突。便于AntDB-M运维管理人员快速定位是否适合建立Hash索引,是否需要进一步优化Hash索引。

5. 限制约束

5.1 不支持范围查询

对于Hash索引,由于索引记录本身不排序,因此不支持范围查询。

注意对索引列字段的范围查询都会进行全表遍历。

5.2 不支持模糊查询

AntDB-M支持固定长度的左前缀匹配。由于Hash计算本身需要精确值,因此不支持模糊匹配。

5.3 索引列不有太多相同值

如果有较多的列有相同值,这些记录将位于同一个索引记录链表中,每次查询都将遍历该列表所有记录进行筛选,数据越多,性能越低。

 

6. 总结

正是Hash索引这种简洁的设计,AntDB-M数据库能够较少的内存和计算即可提供高效的索引能力,提升数据库的访问性能同时大幅降低了系统资源开销。Hash索引算法存在一些使用上的限制主要是由于本身的特性,了解这些特性,可以帮助业务模型设计人员选择合适的索引类型,以最大化提升数据库的性能。

 

关于AntDB数据库

AntDB数据库始于2008年,在运营商的核心系统上,为全国24个省份的10亿多用户提供在线服务,具备高性能、弹性扩展、高可靠等产品特性,峰值每秒可处理百万笔通信核心交易,保障系统持续稳定运行近十年,并在通信、金融、交通、能源、物联网等行业成功商用落地。