[發(fā)明專利]一種索引模型的構建方法及裝置

有效

• 申請?zhí)枺?/td>: 201910703886.9
• 申請日: 2019-07-31
• 公開（公告）號: CN112307266B
• 公開（公告）日: 2023-08-22
• 發(fā)明（設計）人: 李嘉;周文禮
• 申請（專利權）人: 華為云計算技術有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 陳斌

一種索引模型的構建方法及裝置，該方法包括：基于第一數(shù)組預估所述第一數(shù)組對應的索引模型的參數(shù)；基于索引模型的參數(shù)和第一條件對第一數(shù)組進行切分，獲得用于描述索引模型中每個節(jié)點的函數(shù)和用于描述索引模型中的根節(jié)點和每個中間節(jié)點的映射表。因此，采用上述方法構建的索引模型可以實現(xiàn)提升索引模型的查詢速度且減少索引模型占用的內存空間。

技術領域

本申請涉及數(shù)據(jù)庫技術領域，尤其涉及一種索引模型的構建方法及裝置。

背景技術

目前，在存儲、數(shù)據(jù)庫和大數(shù)據(jù)等領域，數(shù)據(jù)快速查找的需求越來越高。業(yè)界主流做法是對數(shù)據(jù)構建索引以加速數(shù)據(jù)查找。主流的索引包括B樹，B+樹等，比如，當前索引主要是通過指紋(fingerprint)關鍵字(key)和邏輯區(qū)塊地址(logical?block?address,lba)key構建的B樹或者B+樹索引，用以支持精確查找和區(qū)間查找，如圖1所示為一個B+樹索引，其中，B+樹是高度為3，每頁存放4條記錄，扇出為5。

隨著人工智能技術的發(fā)展，把機器學習和索引相結合成為一種發(fā)展趨勢，利用數(shù)據(jù)分布信息來構建索引，可以實現(xiàn)加速查找，減少索引空間。

如圖2(a)和圖2(b)所示為一種學習型索引構建示意圖，其主要設計思路為對數(shù)據(jù)按分布進行大致切分，然后在誤差范圍內進行二分查找，具體步驟如下：

1、應用機器學習獲取keys分布的累積分布函數(shù)(Cumulative?DistributionFunction，CDF)函數(shù)：

F(K)＝P(key＝K),表示一個隨機出現(xiàn)的key值不超過給定K的概率。

2、假設N是所要存儲keys的總數(shù)，則p＝F(key)*N就給出了給定key的位置估計。

3、只要上述估計能像B樹一樣保證誤差范圍(Min-err和Max_err)，則上述模型就可替代B樹：對給定key，計算p＝F(key)*N，則在[p-min_err，p+max_err]范圍內可以搜索到該給定key。如圖2(a)所示，pos(即position，簡稱p)。

由上可知，傳統(tǒng)的索引表構建是基于固定規(guī)則的，與數(shù)據(jù)無關，通過嚴謹?shù)囊?guī)則設定，可以保證在最壞情況下索引結果的準確無誤，但是針對大多數(shù)情況，固定規(guī)則過于冗余，占用內存空間較大。而當前的學習型索引構建方法存在更新代價較高的問題，如果數(shù)據(jù)有變化就需要全部重新訓練。

發(fā)明內容

本申請實施例提供一種索引模型的構建方法及裝置，用以優(yōu)化現(xiàn)有的模型構建方法。

第一方面，本申請實施例一種索引構建方法，該方法包括：基于第一數(shù)組預估所述第一數(shù)組對應的索引模型的參數(shù)；基于所述索引模型的參數(shù)和第一條件對所述第一數(shù)組進行切分，獲得用于描述所述索引模型中每個節(jié)點的函數(shù)和用于描述所述索引模型中的根節(jié)點和每個中間節(jié)點的映射表；其中，所述索引模型包括一個根節(jié)點，多個中間節(jié)點和多個葉節(jié)點，所述根節(jié)點對應所述第一數(shù)組，每個中間節(jié)點和每個葉節(jié)點對應所述第一數(shù)組切分后的一段數(shù)組；用于描述所述根節(jié)點的函數(shù)是基于所述第一數(shù)組訓練得到的，用于描述每個中間節(jié)點的函數(shù)是基于該中間節(jié)點對應的數(shù)組訓練得到的，用于描述每個葉節(jié)點的函數(shù)是基于該葉節(jié)點對應的數(shù)組訓練得到的；用于描述所述根節(jié)點的映射表是將所述第一數(shù)組首次切分后得到的每段數(shù)組中的第一個關鍵字計算得到的值構建的鍵值對表；用于描述每個中間節(jié)點的映射表是將該中間節(jié)點對應的段數(shù)組切分后得到的每段數(shù)組中的第一個關鍵字計算得到的值構建的鍵值對表；其中，所述第一條件是指任一用于描述葉節(jié)點的函數(shù)滿足：該葉節(jié)點對應的數(shù)組中任一關鍵字采用用于描述該葉節(jié)點的函數(shù)計算得到的估計下標值與該關鍵字在該葉節(jié)點對應的數(shù)組中的真實下標值的差值的絕對值不超過第一閾值。

采用上述方法構建的索引模型可以實現(xiàn)提升索引模型的查詢速度且減少索引模型占用的內存空間。