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

有效

• 申請(qǐng)?zhí)枺?/td>: 201910703886.9
• 申請(qǐng)日: 2019-07-31
• 公開(kāi)（公告）號(hào): CN112307266B
• 公開(kāi)（公告）日: 2023-08-22
• 發(fā)明（設(shè)計(jì)）人: 李嘉;周文禮
• 申請(qǐng)（專利權(quán)）人: 華為云計(jì)算技術(shù)有限公司
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901
• 代理公司: 北京同達(dá)信恒知識(shí)產(chǎn)權(quán)代理有限公司 11291
• 代理人: 陳斌

1.一種索引構(gòu)建方法，其特征在于，包括：

基于第一數(shù)組預(yù)估所述第一數(shù)組對(duì)應(yīng)的索引模型的參數(shù)；

基于所述索引模型的參數(shù)和第一條件對(duì)所述第一數(shù)組進(jìn)行切分，獲得用于描述所述索引模型中每個(gè)節(jié)點(diǎn)的函數(shù)和用于描述所述索引模型中的根節(jié)點(diǎn)和每個(gè)中間節(jié)點(diǎn)的映射表；

其中，所述索引模型包括一個(gè)根節(jié)點(diǎn)，多個(gè)中間節(jié)點(diǎn)和多個(gè)葉節(jié)點(diǎn)，所述根節(jié)點(diǎn)對(duì)應(yīng)所述第一數(shù)組，每個(gè)中間節(jié)點(diǎn)和每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)所述第一數(shù)組切分后的一段數(shù)組；用于描述所述根節(jié)點(diǎn)的函數(shù)是基于所述第一數(shù)組訓(xùn)練得到的，用于描述每個(gè)中間節(jié)點(diǎn)的函數(shù)是基于該中間節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組訓(xùn)練得到的，用于描述每個(gè)葉節(jié)點(diǎn)的函數(shù)是基于該葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組訓(xùn)練得到的；用于描述所述根節(jié)點(diǎn)的映射表是將所述第一數(shù)組首次切分后得到的每段數(shù)組中的第一個(gè)關(guān)鍵字計(jì)算得到的值構(gòu)建的鍵值對(duì)表；用于描述每個(gè)中間節(jié)點(diǎn)的映射表是將該中間節(jié)點(diǎn)對(duì)應(yīng)的段數(shù)組切分后得到的每段數(shù)組中的第一個(gè)關(guān)鍵字計(jì)算得到的值構(gòu)建的鍵值對(duì)表；

其中，所述第一條件是指任一用于描述葉節(jié)點(diǎn)的函數(shù)滿足：該葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組中任一關(guān)鍵字采用用于描述該葉節(jié)點(diǎn)的函數(shù)計(jì)算得到的估計(jì)下標(biāo)值與該關(guān)鍵字在該葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組中的真實(shí)下標(biāo)值的差值的絕對(duì)值不超過(guò)第一閾值。

2.如權(quán)利要求1所述的方法，其特征在于，還包括：

接收新關(guān)鍵字插入請(qǐng)求；

基于用于描述根節(jié)點(diǎn)和每個(gè)中間節(jié)點(diǎn)的映射表，確定第一葉節(jié)點(diǎn)，所述第一葉節(jié)點(diǎn)為所述新關(guān)鍵字對(duì)應(yīng)的葉節(jié)點(diǎn)，將所述新關(guān)鍵字插入所述第一葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組，獲得更新后的所述第一葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組；

在將所述新關(guān)鍵字插入所述第一葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組后，

若確定用于描述所述第一葉節(jié)點(diǎn)的函數(shù)滿足所述第一條件，則所述索引模型不更新；

若確定用于描述所述第一葉節(jié)點(diǎn)的函數(shù)不滿足所述第一條件，基于更新后的所述第一葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組獲得新的用于描述第一葉節(jié)點(diǎn)的函數(shù)；確定新的用于描述第一葉節(jié)點(diǎn)的函數(shù)滿足所述第一條件，則采用新的用于描述第一葉節(jié)點(diǎn)的函數(shù)更新所述索引模型。

3.如權(quán)利要求1所述的方法，其特征在于，還包括：

接收新關(guān)鍵字插入請(qǐng)求；

基于用于描述根節(jié)點(diǎn)和每個(gè)中間節(jié)點(diǎn)的映射表，確定第一葉節(jié)點(diǎn)，所述第一葉節(jié)點(diǎn)為所述新關(guān)鍵字對(duì)應(yīng)的葉節(jié)點(diǎn)，將所述新關(guān)鍵字插入所述第一葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組，獲得更新后的所述第一葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組；

在將所述新關(guān)鍵字插入所述第一葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組后，確定用于描述所述第一葉節(jié)點(diǎn)的函數(shù)不滿足所述第一條件，基于更新后的所述第一葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組獲得新的用于描述第一葉節(jié)點(diǎn)的函數(shù)；

確定新的用于描述第一葉節(jié)點(diǎn)的函數(shù)不滿足所述第一條件，將所述第一葉節(jié)點(diǎn)作為一個(gè)新的中間節(jié)點(diǎn)，將新的用于描述第一葉節(jié)點(diǎn)的函數(shù)作為用于描述所述新的中間節(jié)點(diǎn)的函數(shù)，將更新后的所述第一葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組切分為多個(gè)數(shù)組，確定用于描述所述新的中間節(jié)點(diǎn)的映射表，并基于所述多個(gè)數(shù)組確定與每個(gè)數(shù)組對(duì)應(yīng)新的葉節(jié)點(diǎn)，用于描述每個(gè)新的葉節(jié)點(diǎn)的函數(shù)；

采用用于描述所述新的中間節(jié)點(diǎn)的函數(shù)和映射表以及用于描述每個(gè)新的葉節(jié)點(diǎn)的函數(shù)更新所述索引模型。

4.如權(quán)利要求1-3任一項(xiàng)所述的方法，其特征在于，還包括：

接收關(guān)鍵字刪除請(qǐng)求；

基于用于描述根節(jié)點(diǎn)和每個(gè)中間節(jié)點(diǎn)的映射表，確定第二葉節(jié)點(diǎn)，所述第二葉節(jié)點(diǎn)為所述關(guān)鍵字對(duì)應(yīng)的葉節(jié)點(diǎn)，將所述關(guān)鍵字從所述第二葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組中刪除，獲得更新后的所述第二葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組；

在將所述關(guān)鍵字從所述第二葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組中刪除后，

若確定用于描述所述第二葉節(jié)點(diǎn)的函數(shù)滿足所述第一條件，則所述索引模型不更新；

若確定用于描述所述第二葉節(jié)點(diǎn)的函數(shù)不滿足所述第一條件，基于更新后的所述第二葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組獲得新的用于描述第一葉節(jié)點(diǎn)的函數(shù)；確定新的用于描述第二葉節(jié)點(diǎn)的函數(shù)滿足所述第一條件，則采用新的用于描述第一葉節(jié)點(diǎn)的函數(shù)更新所述索引模型。

5.如權(quán)利要求1-4任一項(xiàng)所述的方法，其特征在于，所述索引模型的參數(shù)包括所述第一數(shù)組切分成的總段數(shù)、每段數(shù)組平均覆蓋的數(shù)據(jù)點(diǎn)數(shù)以及所述索引模型的第二層包括的中間節(jié)點(diǎn)的數(shù)目。