[發明專利]基于NVM主存的數據索引方法及數據處理系統

有效

• 申請號: 202010064770.8
• 申請日: 2020-01-20
• 公開（公告）號: CN111274456B
• 公開（公告）日: 2023-09-12
• 發明（設計）人: 陳世敏;劉霽航
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國

1.一種基于NVM的數據索引方法，其特征在于，包括：

構建樹狀索引結構；該樹狀索引結構的根節點及內部節點設置于數據處理系統的DRAM主存，該樹狀索引結構的葉子節點設置于該數據處理系統的NVM主存；該葉子節點具有多個且處于同一層，并從左到右以兄弟鏈表連接；該葉子節點包括A索引單元，該A索引單元NVMLine包括M個索引行Line，每個Line具有N個數據項存儲位置；第1個Line為首索引行L_h，L_h的第1個數據項存儲位置為索引頭H，L_h的其余數據項存儲位置為索引項，第2～M-1個Line為中間索引行L_i，L_i的所有數據項存儲位置均為索引項，第M個Line為尾索引行L_t，L_t的第N個數據項為兄弟鏈表指針項S，L_t的其余數據項為索引項；M、N為正整數；索引頭H包括寫入鎖定位lockbit、交替控制位altbit、索引占用位圖bitmap和索引指紋位F，S包括指針S₀和指針S₁；lockbit用于設置當前葉子節點的寫入狀態；altbit用于通過NVM原子寫設置S₀和S₁的其中一個為有效指針，且另一個為無效指針；bitmap，用于分別記錄每個索引項的占用狀態；F為fingerprint數組，用于分別記錄每個索引項的指紋；S的有效指針用于連接該兄弟鏈表；

將新增數據寫入當前葉子節點時，判斷該當前葉子節點的A索引單元是否存在空閑索引項，若存在，則進行數據寫入操作，反之則進行并完成節點分裂操作后再進行該數據寫入操作；

其中，該數據寫入操作包括：若該首索引行存在空閑索引項，則將該新增數據寫入該首索引行的空閑索引項；反之則將該新增數據和該首索引行內存儲的已存數據遷移至該中間索引行和/或該尾索引行的空閑索引項；

該節點分裂操作包括：當葉子節點Node_n的所有索引項都被占用，分配新增葉子節點Node_n'，Node_n'具有與Node_n相同的結構；將Node_n的部分已存數據復制到Node_n'的索引項，并修改Node_n'的首索引行L_h'索引頭H'的索引占用位圖bitmap'；將Node_n'的兄弟鏈表指針項S'的有效指針指向Node_n的右兄弟葉子節點Node_n+1，將Node_n的兄弟鏈表指針項S的無效指針指向Node_n'；在該NVM主存中持久化Node_n'；以NVM原子寫設置altbit以將S指向Node_n'的指針設置為有效指針，并將S指向Node_n+1的指針設置為無效指針；將該部分已存數據在Node_n的索引項清空為空閑索引項，并以NVM原子寫修改bitmap。

2.如權利要求1所述的數據索引方法，其特征在于，該葉子節點還包括至少一個B索引單元NVMLine'，設置于每個NVMLine'包括M個Line，每個Line具有N個數據項存儲位置；

NVMLine'的第1個Line的第1個數據項存儲位置為首索引頭H0，NVMLine'的第M個Line的第N個數據項存儲位置為尾索引頭H1；

H0包括索引占用位圖bitmap'和索引指紋位F'；H1具有與H0相同的結構；通過NVM原子寫設置H的altbit，以設置H₀和H₁的其中一個為有效索引頭，且另一個為無效索引頭，其中，有效索引頭的bitmap'用于分別記錄當前NVMLine'的每個索引項的占用狀態；有效索引頭的F'為fingerprint數組，用于分別記錄當前NVMLine'的每個索引項的指紋。

3.如權利要求1所述的數據索引方法，其特征在于，該數據索引方法還包括：

僅當寫入鎖定位lockbit設置為鎖定狀態且退出并發控制的硬件事務后，進行獨占葉子節點的數據寫入操作。