[發明專利]數據庫子串過濾索引系統及其構建、查詢方法

無效

• 申請號: 201210202879.9
• 申請日: 2012-06-19
• 公開（公告）號: CN102831146A
• 公開（公告）日: 2012-12-19
• 發明（設計）人: 蔡華林;馮柯;徐昶;何清法;周麗霞;蔣志勇;毛云青;趙殿奎;李海峰
• 申請（專利權）人: 天津神舟通用數據技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 天津盛理知識產權代理有限公司 12209
• 代理人: 王利文

1.一種數據庫子串過濾索引系統，其特征在于：包括將導入數據進行分片數據存儲并從每個分片數據中提取出描述分片數據的子串特征構建一個或多個子串特征過濾位圖的分片式數據存儲模塊，以及用于存儲以子串特征過濾位圖為子串特征索引的過濾索引存儲模塊。

2.根據權利要求1所述的數據庫子串過濾索引系統，其特征在于：所述分片數據存儲的存儲方式為：每個分片數據作為數據庫中的一行存儲，對于同一分片數據盡可能連續存儲；所述子串特征索引的數據存儲方式為：包括對多個不同小子串特征位圖的存儲，對于同一個小子串特征位圖采用連續存儲。

3.根據權利要求1所述的數據庫子串過濾索引系統，其特征在于：所述的分片數據和子串特征索引采用壓縮后的數據進行存儲。

4.一種根據權利要求1～3中任一項所述的數據庫子串過濾索引系統的構建方法，包括以下步驟：

步驟1：對所有導入數據進行分片存儲；

步驟2：對于每個分片數據，使用小子串特征值建立小子串特征位圖作為子串特征的概要知識，分別為每個需要建子串過濾索引的列建立一個或多個子串特征過濾位圖，然后分別進行保存；

步驟3：為每個小子串特征位圖預存足夠連續物理空間，在內存中建立一個或多個小子串特征位圖的緩存，當緩存積累到一定大小時將位圖數據回刷到物理存儲；

步驟4：將所有分片數據包的所有子串特征位圖，共同構成子串過濾索引。

5.根據權利要求4所述的數據庫子串過濾索引系統，其特征在于：所述步驟1對導入數據進行分片存儲包括以下處理方式：按導入順序每隔一定行數作為一個分片，或者按照哈希或其他規則進行聚集分片，或是對緩沖區內的導入數據排序后按順序分片。

6.根據權利要求5所述的數據庫子串過濾索引系統，其特征在于：所述步驟2建立小子串特征位圖方法為：

（1）構建一個稀疏位圖，該稀疏位圖的位數與要索引數據的字節數相關；

（2）為數據每一行指定長度為K的小子串計算出特征值；

（3）將特征值映射到稀疏位圖上進行置位；

（4）所有小子串映射置位后的結果位圖即為小子串特征位圖。

7.根據權利要求6所述的數據庫子串過濾索引系統，其特征在于：所述多個子串特征位圖的特征值計算方法采用各種不同哈希算法或指定不同的K值進行計算；所述特征值到位圖某一位的映射使用取模方法。

8.一種根據權利要求1～3中任一項所述的數據庫子串過濾索引系統的查詢查詢方法，包括以下步驟：

步驟1、獲取子串過濾索引包含的所有子串特征過濾位圖并創建分片數據的過濾結果位圖；

步驟2、遍歷過濾結果位圖，獲取未被過濾的分片數據，遍歷查詢條件對應列，判斷真實數據是否符合子串查詢條件，若符合則返回該行數據。

9.根據權利要求8所述的數據庫子串過濾索引系統，其特征在于：所述步驟1創建分片數據的過濾結果位圖采用如下方法實現：

（1）假設子串特征位圖所對應的小子串長度為K，將待查詢子串分解得到長度為K的所有小子串作為過濾條件，計算這些小子串特征值，映射得到這些值在子串特征位圖中所處的位置下標；遍歷每個分片數據對應的該子串特征位圖，判斷位圖中所有小子串對應下標所指向位置是否被置位，只要有一個未被置位即可確定相應分片數據被過濾；

（2）為所有分片數據包按順序建立一個過濾結果位圖，在使用每個子串過濾結果位圖進行過濾時，將被過濾的分片數據包對應位置置位，實現使用位圖進行過濾結果的保存。

10.根據權利要求8所述的數據庫子串過濾索引系統，其特征在于：所述對子串特征過濾位圖進行分片過濾時，采用多個特征過濾位圖同時進行并將結果進行合并然后置位到結果位圖中，或者采用一個子串特征過濾位圖處理完后再使用下一個進行過濾并將結果進行合并；若被過濾掉的分片數據占所有分片數據的比例達到一定閾值時，停止對剩余位圖的過濾處理。