[發明專利]一種LSM樹的優化方法、裝置及計算機設備

有效

• 申請號: 201810550710.X
• 申請日: 2018-05-31
• 公開（公告）號: CN108804625B
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 陽振坤;席華鋒;韓富晟;肖金亮
• 申請（專利權）人: 阿里巴巴集團控股有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/215;G06F16/23
• 代理公司: 北京博思佳知識產權代理有限公司 11415
• 代理人: 林祥

公開了一種LSM樹的優化方法、裝置及計算機設備，該方法包括：確定出LSM樹中，所指向的數據已被刪除的目標葉子節點；在所述LSM樹的動態數據中，為所述目標葉子節點添加刪除標記。

技術領域

本說明書實施例涉及數據處理技術領域，尤其涉及一種LSM樹的優化方法、裝置及計算機設備。

背景技術

LSM樹(Log-Structured Merge Tree，日志結構的合并樹)是一種基于硬盤的數據結構，其包括動態數據與靜態數據，動態數據和靜態數據存儲的是數據的修改增量。在訪問LSM樹的過程中，依次讀取其動態數據和靜態數據，將所讀取到的結果進行合并，以得到最終的讀取結果。

由于LSM樹保存的是數據的修改增量，從而當LSM樹中保存有大量的用于表示數據已被刪除的修改增量時，在進行數據讀取過程中，需要遍歷大量的無用數據，才能讀取到有效的數據，這也就導致數據的讀取性能下降。

發明內容

針對上述技術問題，本說明書實施例提供一種LSM樹的優化方法、裝置及，技術方案如下：

根據本說明書實施例的第一方面，提供一種LSM樹的優化方法，所述方法包括：

確定出LSM樹中，所指向的數據已被刪除的目標葉子節點；

在所述LSM樹的動態數據中，為所述目標葉子節點添加刪除標記。

根據本說明書實施例的第二方面，提供一種LSM樹的優化裝置，所述裝置包括：

目標確定模塊，用于確定出LSM樹中，所指向的數據已被刪除的目標葉子節點；

第一添加模塊，用于在所述LSM樹的動態數據中，為所述目標葉子節點添加刪除標記。

根據本說明書實施例的第三方面，提供一種計算機設備，包括存儲器、處理器及存儲在存儲器上并可在處理器上運行的計算機程序，其中，所述處理器執行所述程序時實現本說明書實施例提供的LSM樹的優化方法。

本說明書實施例所提供的技術方案，通過確定出LSM樹中，所指向的數據已被刪除的目標葉子節點，在該LSM樹的動態數據中，為所確定出的目標葉子節點添加刪除標記，由于在對LSM樹進行數據訪問時，首先訪問LSM樹的動態數據，再訪問LSM樹的靜態數據，從而在動態數據中，為那些所指向的數據已被刪除的目標葉子節點添加刪除標記，可以實現在訪問動態數據時，直接跳過具有刪除標記的葉子節點，從而提高數據訪問效率，進一步，在訪問靜態數據時，也無需重復訪問具有刪除標記的葉子節點，從而提高數據訪問效率。

應當理解的是，以上的一般描述和后文的細節描述僅是示例性和解釋性的，并不能限制本說明書實施例。

此外，本說明書實施例中的任一實施例并不需要達到上述的全部效果。

附圖說明

為了更清楚地說明本說明書實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本說明書實施例中記載的一些實施例，對于本領域普通技術人員來講，還可以根據這些附圖獲得其他的附圖。

圖1為LSM樹的一種示例；

圖2為本說明書一示例性實施例提供的一種LSM樹的優化方法的實施例流程圖；

圖3為LSM樹的靜態數據的一種示例；

圖4為在LSM樹的動態數據中添加刪除標記的一種示例；

圖5為在LSM樹的動態數據中添加刪除標記的另一種示例；

圖6為本說明書一示例性實施例提供的一種LSM樹的優化裝置的實施例框圖；