数据库性能优化必读，AntDB-M数据库的哈希索引设计

数据库加快访问速度的关键技术之一就是索引，索引的设计及使用方式极大程度上影响了数据库的性能。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：索引记录链表

3. 索引处理

3.1 持久化

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

3.2 初始化

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

3.3 插入索引记录

表插入一条记录时，会先插入表记录，再插入索引记录。新的记录会添加到索引链表头部，以提高插入速度。

l 普通索引

图3：普通索引插入

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

关于AntDB数据库

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

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