索引机制合并方法、搜索方法、装置及设备

摘要

本发明公开了一种索引机制合并方法、搜索方法、装置及设备，属于计算机技术领域。所述方法包括：在L_i达到容量上限后，检测L_i+1是否正在合并；若检测结果为所述L_i+1正在合并，则检测L_i+1’是否已经达到容量上限；若检测结果为所述L_i+1’未达到容量上限，则将L_i与L_i+1’合并。本发明通过在L_i达到容量上限后，若L_i+1正在合并，则将L_i与L_i+1’进行合并；解决了现有技术中索引机制FD树在合并过程中占用较长时间的问题；由于在L_i+1正在合并的过程中，可以同时进行L_i与L_i+1’的合并过程，因此实现了多线程合并，达到了可以很大程度上提高了合并速率的效果。

主权项

一种存储装置，其特征在于，所述存储装置包括至少三层存储单元，第0层存储单元位于内存中，第i层存储单元位于闪存中，每层存储单元包括主数据区，其中：所述第0层存储单元中的主数据区为有序搜索树，当所述第0层存储单元中存在从数据区时，所述从数据区为有序搜索树，所述有序搜索树包括数据记录和/或页面记录；所述第i层存储单元中的主数据区为有序搜索树或有序数组，当所述第i层存储单元中存在从数据区时，所述从数据区为有序数组，所述有序搜索树包括页面记录，所述有序数组包括数据记录和/或页面记录；所述数据记录包括键值和记录值，所述页面记录包括键值和页面地址；当所述第i层存储单元中存在从数据区L_i’时，所述L_i’为所述第i层存储单元的第一搜索数据区，所述第i层存储单元中的主数据区L_i为所述第i层存储单元的第二搜索数据区；当所述第i层存储单元中不存在所述L_i’时，所述L_i为所述第i层存储单元的所述第一搜索数据区；所述L_i按序保存指向第i+1层存储单元中的第一搜索数据区的所有页面对应的页面记录；当所述第i+1层存储单元中的第一搜索数据区为有序搜索树时，则所述L_i的页面记录是无效记录；所述L_i’按序保存指向所述L_i的所有页面对应的页面记录；当所述L_i为有序搜索树时，则所述L_i’的页面记录为无效记录，其中，所述i为大于0的自然数。