[發明專利]比特序列檢索裝置、檢索方法以及程序

有效

• 申請號: 200780025563.4
• 申請日: 2007-06-15
• 公開（公告）號: CN101484895A
• 公開（公告）日: 2009-07-15
• 發明（設計）人: 新莊敏男
• 申請（專利權）人: 新葉股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京三友知識產權代理有限公司
• 代理人: 黃綸偉

技術領域

本發明涉及從比特序列的集合中檢索期望的比特序列的檢索裝置， 特別是涉及對存儲比特序列的數據結構進行設計來實現檢索速度等的提 高的技術領域。

背景技術

近年，社會的信息化不斷發展，大規模的數據庫在各處利用起來。 為了從這種大規模的數據庫中檢索記錄，通常是將與存儲有各記錄的地 址相對應的記錄內的項目用作索引關鍵字來進行檢索，檢索出期望的記 錄。并且，全文檢索中的字符串也能視為文件的索引關鍵字。

而且，由于這些索引關鍵字利用比特序列來表現，因而數據庫的檢 索可歸結于比特序列的檢索。

為了高速進行上述比特序列的檢索，以往做法是，對存儲比特序列 的數據結構進行種種設計。作為這種設計之一，公知的是Patricia(帕特 里希亞)樹這樣的樹結構。

圖17示出在上述現有的檢索處理中使用的Patricia樹的一例。Patricia 樹的節點構成為包含索引關鍵字、檢索關鍵字的檢查比特位置、以及左 右的鏈接指針。盡管未作明示，然而當然在節點內包含有用于對與索引 關鍵字對應的記錄進行存取的信息。

在圖17的例子中，保持索引關鍵字“100010”的節點1750a為根節點， 其檢查比特位置是0。節點1750a的左鏈接1740a與節點1750b連接，右 鏈接1741a與節點1750f連接。

節點1750b保持的索引關鍵字是“010011”，檢查比特位置1730b是1。 節點1750b的左鏈接1740b與節點1750c連接，右鏈接1741b與節點1750d 連接。節點1750c保持的索引關鍵字是“000111”，檢查比特位置是3。節 點1750d保持的索引關鍵字是“011010”，檢查比特位置是2。

從節點1750c用實線連接的部分表示節點1750c的左右鏈接指針， 未進行虛線連接的左指針1740c表示該欄是空欄。進行了虛線連接的右 指針1741c的虛線的連接目的地表示指針所指示的地址，在當前情況下 表示右指針指定節點1750c。

節點1750d的右指針1741d指定節點1750d自身，左鏈接1740d與 節點1750e連接。1750e保持的索引關鍵字是“010010”，檢查比特位置是 5。節點1750e的左指針1740e指定節點1750b，右指針1741e指定節點 1750e。

并且，節點1750f保持的索引關鍵字是“101011”，檢查比特位置1730f 是2。節點1750f的左鏈接1740f與節點1750g連接，右鏈接1741f與節 點1750h連接。

節點1750g保持的索引關鍵字是“100011”，檢查比特位置1730g是5。 節點1750g的左指針1740g指定節點1750a，右指針1741g指定節點 1750g。

節點1750h保持的索引關鍵字是“101100”，檢查比特位置1730h是3。 節點1750h的左指針1740h指定節點1750f，右指針1741h指定節點1750h。

在圖17的例子中，采用這樣的結構：隨著從根節點1750a開始對樹 進行向下遍歷，各節點的檢查比特位置增大。

當使用某檢索關鍵字進行檢索時，從根節點開始依次檢查由各節點 所保持的檢索關鍵字的檢查比特位置，判定檢查比特位置的比特值是1 還是0，在是1時搜索右鏈接，在是0時搜索左鏈接。然后，當鏈接目的 地的節點的檢查比特位置不大于鏈接源的節點的檢查比特位置時，即， 鏈接目的地回到上方而不是下方時(將圖17中虛線所示的該后退的鏈接 稱為反向鏈接)，進行鏈接目的地的節點的索引關鍵字和檢索關鍵字的比 較。能夠保證在比較結果是相同時檢索成功，在比較結果是不相同時檢 索失敗。

如上所述，在使用Patricia樹的檢索處理中，有以下等優點：只通過 所需要的比特的檢查就能進行檢索，以及關鍵字全體的比較只要一次就 行，然而具有以下等缺點：由于必定有來自各節點的2個鏈接而使存儲 容量增大，由于反向鏈接的存在而使判定處理復雜化，在通過反向鏈接 返回之后才與索引關鍵字進行比較而使得檢索處理延遲以及使追加刪除 等數據維護困難。