高并发索引B+链表数据结构的设计与实现方法

摘要

本发明公开了一种高并发索引B+链表数据结构的设计与实现方法，该方法包括：同时使用基于数组的和基于元素得到数据结构；对于数据结构的非叶子节点，采用预设的B+树数据结构，置放于DRAM中，使位于DRAM上的非叶子节点保证访问的局部性；对于数据结构的叶子节点，采用单向链表数据结构，置放于NVM中，使位于NVM上的叶子节点避免排序和平衡的开销。该方法使用基于数组的数据组织形式和基于元素的数据组织形式、链表数据结构构建索引数据结构的叶子节点、B+树数据结构构建索引数据结构的内部节点、跳表数据结构去除排序和平衡的操作，可以实现无锁并发机制和有效空间管理，并保证高效的并发访问性能和快速的系统恢复。