[發明專利]一種應對可追加數據的索引方法

在審

• 申請號: 201710365878.9
• 申請日: 2017-05-23
• 公開（公告）號: CN108959308A
• 公開（公告）日: 2018-12-07
• 發明（設計）人: 蔣步星
• 申請（專利權）人: 北京潤乾信息系統技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明提供了一種應對可追加數據的索引方法。當索引數據產生后，如果又產生了新的數據追加到了數據集，這時就需要對索引數據進行同步修改。如果重寫索引數據，當歷史數據特別巨大時，索引數據也可能特別巨大，這時追加少量數據也會導致重寫整個索引數據，導致數據更新性能低。為了解決這個問題特設計了雙索引結構，即在索引數據中維護了兩段排序索引，現有數據一段，后追加數據一段，當追加的數據在追加索引中累積達到一定量時則重新生成索引數據把兩段索引合成一段。當使用索引數據查詢數據時，把兩段索引的查詢結果進行合并就得到了所有滿足條件的記錄了。

技術領域

本發明涉及索引，更具體地來說，特別涉及一種應對可追加數據的索引方法。

背景技術

計算機科學的發展提供了很多優秀的查找算法，例如二分查找(binary search)、二叉樹查找(binary tree search)等。如果稍微分析一下會發現，每種查找算法都只能應用于特定的數據結構之上，例如二分查找要求被檢索數據有序，而二叉樹查找只能應用于二叉查找樹上，但是數據本身的組織結構不可能完全滿足各種數據結構(例如，理論上不可能同時將兩列都按順序進行組織)，所以，在數據之外，系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現高級查找算法。這種數據結構，就是索引。

索引是一種單獨的、物理的對數據集中一列或多列的值進行排序的一種存儲結構，它是某個數據集中一列或若干列值的集合和相應的指向數據集中物理標識這些值的數據頁的邏輯指針清單。索引的作用相當于圖書的目錄，可以根據目錄中的頁碼快速找到所需的內容。

索引提供指向存儲在數據集的指定列中的數據值的指針，然后根據您指定的排序順序對這些指針排序。使用索引可以找到特定值，然后順指針找到包含該值的行。

當數據集中有大量記錄時，若要對數據集進行查詢，第一種搜索信息方式是全數據集搜索，是將所有記錄一一取出，和查詢條件進行一一對比，然后返回滿足條件的記錄，這樣做會消耗大量系統時間，并造成大量磁盤I/O操作；第二種就是在數據集中建立索引，然后在索引中找到符合查詢條件的索引值，最后通過保存在索引中的ROWID(相當于頁碼)快速找到數據集中對應的記錄。

索引被用作包含所關心數據的數據集指針。通過一個索引，能從數據集中直接找到一個特定的記錄，而不必連續順序掃描這個數據集，一次一個地去查找。對于大的數據集，索引是必要的。沒有索引，要想得到一個結果要等好幾個小時、好幾天，而不是幾秒鐘。當經常查詢某列或某幾列中的數據時，也需要在數據集上創建索引。索引將占用磁盤空間，并且影響數據更新的速度。但是在多數情況下，索引所帶來的數據檢索速度優勢大大超過它的不足之處。

目前排序結構的索引存在的技術缺點是，當索引數據產生后，如果又產生了新的數據追加到了數據集，這時就需要對索引數據進行同步修改。如果重寫索引數據，當現有數據特別巨大時，索引數據也可能特別巨大，這時追加少量數據也會導致重寫整個索引數據，導致數據更新性能低。

現有的另一種索引手段是以B樹為結構，B樹的特性：關鍵字集合分布在整棵樹上；任何一個關鍵字出現而且只出現在一個結點中；搜索有可能在非葉子結點結束；其搜索性能等價于在關鍵字全集內做一次二分查找；自動層次控制。當數據集在面積的刪除和增加的時候，需要動態的修改B樹中的索引結構，為了實現B樹的平衡，達到搜索二分法優化查詢的作用，需要在B樹非頁結點中每個結點都留出一定的空間來記錄新數據或者描述刪除數據，這一部分被稱作填充因子。B樹的缺點在于實現過于復雜；在數據情況不好時B樹不夠平衡；當對其進行更新插入刪除時，就需要在物理上移動以調整B樹；上述缺點導致數據更新性能低。

現有技術存在的兩種索引手段都有各自的優缺點，但是都不合適應用在只有追加而沒有刪除和修改這種情況下，針對這一問題本發明創造研發出新的一種索引手段，簡單、高效的處理數據追加時索引的修改，保證數據更新性能高。

發明內容