[發明專利]高并發索引B+鏈表數據結構的設計與實現方法

有效

• 申請號: 201811129622.9
• 申請日: 2018-09-27
• 公開（公告）號: CN109407978B
• 公開（公告）日: 2020-07-28
• 發明（設計）人: 舒繼武;陸游游;胡慶達;劉昊
• 申請（專利權）人: 清華大學
• 主分類號: G06F3/06
• 分類號: G06F3/06;G06F12/02
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張潤

1.一種高并發索引B+鏈表數據結構的設計與實現方法，其特征在于，包括以下步驟：

同時使用基于數組的數據組織形式的和基于元素的數據組織形式得到數據結構；

對于所述數據結構的非葉子節點，采用預設的B+樹數據結構，并置放于DRAM中，以使位于所述DRAM上的非葉子節點保證訪問的局部性；以及

對于所述數據結構的葉子節點，采用單向鏈表數據結構，并置放于NVM中，以使位于所述NVM上的葉子節點避免排序和平衡的開銷；

粗粒度的所述B+樹數據結構使用細粒度的閉鎖和優化的并發控制，而細粒度的鏈表節點使用無鎖的并發控制機制，同時通過鏡像鍵和去中心的鍵計數器和并發的分割優化增強可擴展性；

所述數據結構采用差分的并發控制機制，其中，在基于數組的數據組織形式層面中使用基于鎖的并發控制機制，并且在基于元素數據組織形式的層面中使用無鎖并發控制機制，樂觀的并發控制機制保證讀不需要額外的鎖機制；

在所述基于數組的數據組織形式層面中，在并發的讀和寫之間采用所述樂觀的并發控制機制，在所述基于元素的數據組織形式層面中，對于并發的寫操作采用細粒度鎖方法，使用一個插入和分割標志位標識該節點是否為插入節點或已被刪除，同時根節點標識和葉子節點標識該節點是根節點還是葉子節點。

2.根據權利要求1所述的高并發索引B+鏈表數據結構的設計與實現方法，其特征在于，基于元素的數據結構以單個對象的粒度進行分配和釋放，以通過原子性的指針操作避免因復雜的版本操作而造成的低空間利用率，并且所述基于數組的和基于元素的數據結構的每一個數組均有一個受限的鍵值對對數。

3.根據權利要求1所述的高并發索引B+鏈表數據結構的設計與實現方法，其特征在于，所述鏈表數據結構為一個排序的鏈表，其右兄弟指針在B+鏈表的底層，每一個基于元素的指針只有一個鍵值對，其中，所述鏈表按照元素有序排列通過兄弟節點指針互相引用，同時葉子節點鏈表維持預設數量的節點數，其中，在發生異常時，通過位于所述NVM上的葉子構建位于所述DRAM上的內部節點，其方法是遍歷葉子節點，以找出其對應的兄弟節點的相互關系，重新構建位于所述DRAM中的數據結構。

4.根據權利要求1所述的高并發索引B+鏈表數據結構的設計與實現方法，其特征在于，所述數據結構的每一個內部節點擁有一套預設的排序鍵序列，連續地保存操作數以保證高緩存命中率，以保證查找的平均時間復雜度為O(log n)。

5.根據權利要求1所述的高并發索引B+鏈表數據結構的設計與實現方法，其特征在于，所述葉子節點在內部節點的最下層通過兩個相鄰的指針連接形成一個葉子節點組，每個葉子節點組有一個預設的大小LNG，當葉子節點組大小大于或者小于預設閾值時，將產生分裂或者合并，分裂或者合并操作只需要從上一層的內部節點增加或者刪除一個鍵指針對。

6.根據權利要求1所述的高并發索引B+鏈表數據結構的設計與實現方法，其特征在于，在連續的內存空間中分別獨立存儲鍵數組和子節點指針數組，以此減少從每一個節點中數據預取的量，其中，所述數據結構使用SIMD處理加速查詢處理。

7.根據權利要求4所述的高并發索引B+鏈表數據結構的設計與實現方法，其特征在于，基于數組的層次占據整個數據結構空間的比例根據LNG的大小得到。