DLB+树:一种基于双叶子结点的内存数据库索引算法

摘要

内存数据库将数据存储在内存中,相比于传统磁盘数据库在性能得到了极大的提升,但是由于内存数据库与传统数据库的性能瓶颈的差异,传统B+树索引算法已经不适用于内存数据库,所以T树,CSS树,CSB+树等索引算法相继被提出,但是始终没有对索引的范围查询以及空间利用率进行优化.本文通过将B+树的叶子结点扩展为双叶子结点,并相应改进了算法策略,最终得到一种更适用于范围查询且有较高空间利用率的索引算法.实验证明当查询数据达到一定数量,其范围查询效率是B+树查询效率的一倍.