Page 83 - 《软件学报》2021年第5期

尤勇 等:一种监控系统的链路跟踪型日志数据的存储设计 1307

Fig.2 Structure of hash indexing
图 2 Hash 索引结构
在创建 hash 索引时,首先使用哈希函数对 LogView 的 id 值计算得到哈希值,再对哈希值与数组容量大小进
行位运算,得到的值即为它在数组空间中的下标位置;之后新建一个节点,并将 id 值、地址信息记录到节点中;
最后,将节点添加到链表尾部即可.
在使用 hash 索引查询 LogView 时,利用 id 值查询,起始同样是计算哈希值、位运算定位下标两个步骤,下
标定位过程的时间复杂度为 O(1),这也是 hash 索引的性能突出优势.在获取到下标值之后,即可找到对应的链
表,最后对链表进行遍历并一一比对.
hash 索引存在以下优缺点.
• 优点:索引的设计简捷、高效;使用 hash 函数定位数组空间的下标时,时间复杂度为 O(1).
• 缺点:(1) 查询效率不稳定,部分查询效率非常快,而部分则非常慢.这是因为 hash 索引结构中的链表部
分的长度并不平均.如图 2 所示,图中的 4 条链表中的节点数目差距较大,所以在链表的遍历时所用的
时间也不一致.所以,一个合适的哈希函数能够让 LogView 在哈希表中的分布更加均匀(即数组中不存
在空洞、链表长度较平均),而这个函数的选择是比较困难的.(2) 在索引结构的数组部分存在较多的空
洞,如图 2 所示,数组中较多的空间并没有用到,即较多的内存空间内浪费了.(3) 针对数组部分的 hash
函数难以找到合适的,此外,数组大小的初始化值同样不好定义,并且在数组空间满了之后,需要对数组
空间进行扩容操作,实现上同样相对麻烦.最后,在链表的节点中,需要记录的信息较多,除了地址信息
外,还需要额外将 id 值记录下来,这样在遍历链表时才能进行一一对比确定是否为指定的 LogView.
2.2.2 B+树索引
B+树 [22] 是当前主流数据库存储引擎(比如 Innodb)中常用的索引结构.在构建 B+树时,需要不断添加树节点
以及调整树的结构;而在查询时,则直接根据树节点数据定位到根节点,获取到根节点中存储的地址信息即可.
如图 3 所,B+树索引通常在 2~4 层,所以磁盘的 IO 次数也在 2~4 次,查询性能很高.

Fig.3 Indexing structure of B+ tree
图 3 B+树索引结构

在使用 B+树的构建索引结构时,同样需要针对 id 值建立索引树,B+树索引结构存在以下优缺点.
• 优点:B+树索引的查询性能稳定且高效;不同于 hash 索引需要预定义较大的内存空间并且可能会发生