一种高效的新型内存索引结构处理方法

摘要

本发明公开了一种高效的新型内存索引结构处理方法。在跳表处理前，通过统计信息计算查询分布以及数据分布情况；选择插入跳表结构的哨兵节点；通过求解跳表在插入节点后的最小平均操作代价，得到最优的哨兵节点的配置结果；在底层跳表结构中插入这些哨兵节点，接着在底层跳表结构中的哨兵节点插入完毕后，通过Bulkload方法自底向上建立上层CSB+树结构，对哨兵节点的快速定位；对于每一条需要查询或者插入的数据，通过上层CSB+树结构，找到最近哨兵节点，从此开始对跳表进行操作。本发明方法在保留传统跳表结构实现简单、并发性好、适合范围查询等优势的基础上，提升了整个操作过程对缓存的利用率，从而明显提升了内存索引的性能。