一種采用雙向有序鏈表存儲的動態(tài)編碼位圖索引方法

王書海， 劉桂蘭， 綦朝暉

（1．石家莊鐵道大學 信息科學與技術學院，河北 石家莊 050043；（2．河北省大型結構健康診斷與控制實驗室，河北 石家莊 050043）

0 引言

數(shù)據(jù)量的快速增長對數(shù)據(jù)檢索效率提出了新的挑戰(zhàn)。索引被證明是用于提高數(shù)據(jù)檢索效率的關鍵技術，而位圖索引依據(jù)其獨特的位向量編碼方式，在數(shù)據(jù)檢索中得到廣泛使用。位圖索引按其編碼處理方式可分為簡單位圖索引和編碼位圖索引。

簡單位圖索引依據(jù)其簡單的編碼方式即位向量，使其可以充分利用計算機邏輯運算的能力。簡單位圖索引中屬性值的編碼位數(shù)和屬性基數(shù)有直接的關系，存儲空間和查詢時間都與基數(shù)成正比［1－2］。同時也可以看出其弊端，當屬性基數(shù)很大時，位串就會比較長，在時間和空間上開銷都會很大。針對該問題學者們提出了很多數(shù)據(jù)壓縮技術，諸如WAH、BBC、分段編碼，以及將WAH 和分段編碼相結合的方法等［3－5］。但壓縮率與0和1位串的連續(xù)分布性有直接關系，并沒有使編碼空間得到充分的利用。

編碼位圖索引是通過對簡單位圖索引位串中只有一個1、多個0的情況進行改進，其位數(shù)等于先對屬性的基數(shù)進行對數(shù)運算，然后將其向上取整的結果［6－7］?，F(xiàn)有的編碼位圖索引方式是采用對屬性進行靜態(tài)的編碼，這樣在使用數(shù)據(jù)表之前，屬性所有取值情況的編碼值都已經(jīng)存在，并且在修改數(shù)據(jù)表時，即使沒有某屬性值也會為其分配編碼值，在一定程度上浪費了存儲空間。另外，目前已有的編碼位圖索引技術大都是基于B＋樹建立的索引存儲結構［8－9］。B＋樹憑借其平衡的數(shù)據(jù)結構使其在查找過程中可以充分利用二分查找的方式提高其檢索效率，從而得到了大家的認同。但在B＋樹結構中除了含關鍵字信息外，還增加了非葉子節(jié)點中的索引信息。當查詢數(shù)據(jù)時，即使非葉子節(jié)點的關鍵值等于查找值，也必須搜索到葉子節(jié)點才完成檢索操作。例如Value從1到10，節(jié)點長度為3的B＋樹的組織結構如圖1所示。

圖1 基于u檢驗方法的狀態(tài)檢修流程圖

從圖1可以看出，使用B＋樹結構存儲數(shù)據(jù)，不僅需要存儲所有數(shù)據(jù)節(jié)點，同時增加了標識數(shù)據(jù)最值的邊節(jié)點。

本文提出一種新的雙向有序鏈表存儲的動態(tài)編碼位圖索引方法（BLS－DEBI，Dynamic Encoding Bitmap Index by Bi－ordered List Storage）。該方法在索引存儲結構上，采用雙向有序鏈表結構存儲索引以節(jié)約存儲空間，在位圖編碼方式上，采用動態(tài)編碼的方式對位圖索引進行編碼以減少編碼位串長度。

1 動態(tài)編碼位圖索引方法

1．1 基本原理

采用雙向鏈表存儲的動態(tài)編碼位圖索引方法指的是對建。立索引的屬性采用動態(tài)編碼的方式賦予編碼值，并將其存儲在映射表中。同時，使用雙向有序鏈表存儲索引及其物理位置的對應關系。通過該方法，在很大程度上改善了簡單位圖索引空間利用率不足的問題。同時由于編碼仍采用二進制編碼的方式，仍可利用計算機邏輯運算的優(yōu)勢。

動態(tài)編碼位圖索引。映射表初始狀態(tài)為空，隨著數(shù)據(jù)元組的插入，需要建立索引的屬性列F 取值情況增多。在維護屬性列F索引信息時，根據(jù)剛插入的記錄在屬性F 上的投影V（F），首先遍歷映射表，查看是否已有V（F）對應的編碼值，若不存在，則需要判斷屬性值增加前和增加后標識位長度是否相同，如果相同則直接將映射表中最后元組的編碼值二進制表示加1即為新編碼值，否則首先在已有的編碼值前加0以保證編碼位數(shù)相同，再將映射表中最后元組的編碼值二進制表示加1的結果賦予新的元組編碼值，并將V（F）和編碼值對應關系添加到映射表中。

采用雙向有序鏈表存儲編碼值。在最初狀態(tài)，數(shù)據(jù)表為空，此時鏈表也為空。隨著數(shù)據(jù)元組的插入，需要建立索引的屬性列F 取值情況增多。在維護屬性列F 索引信息時，根據(jù)剛插入的記錄在屬性F 上的投影V（F），首先遍歷映射表，查看是否已有V（F）對應的編碼值，如果已經(jīng)存在，則查詢鏈表，找到對應編碼值，直接將其物理位置標識（如主鍵）記錄到對應節(jié)點內。否則需要首先在映射表中增加新編碼值，同時在鏈表中新增節(jié)點，存儲索引值和元組的對應關系。具體操作見例1。

例1：假設存在一個學生基本信息表T（學號，性別，省份）。不失一般性現(xiàn)分別對性別、省份列建立位圖索引。設屬性的基數(shù)用C（屬性名）表示，編碼需要的位數(shù)用L（屬性名）表示。

現(xiàn)針對省份信息建立索引。目前中國省份屬性共有34個不同值，如果采用簡單位圖索引需要34位位串表示，若采用靜態(tài)編碼位圖索引，則默認每個屬性值需要log234＝6位位串，索引壓縮率為34／6。若采用BLS－DEBI的方式，則僅需要log2Dis（F）位位串，其中Dis（F）表示表中已有的屬性列F（這里F代表省份）取值的無重復個數(shù)，Dis（F）的最大取值為屬性F 的所有取值情況C（F）。存儲結構如圖2所示。將屬性基數(shù)和位串位長度建立函數(shù)關系，簡單位圖索引可表示為L（F）＝mC（F）（m 表示編碼壓縮率，0＜m≤1）的形式。編碼位圖索引可簡單的表示為L（F）＝m log2C（F）（m 表示編碼壓縮率，0＜m≤1）的形式，如圖3所示。

圖2 存儲省份屬性使用的雙向有序鏈表結構

由圖2，圖3可知，①采用雙向有序鏈表存儲索引，查詢操作只需在鏈表結構中利用二分查找法搜索即可得到滿足條件元組的主鍵值；②編碼位圖索引所需位串長度L（B）比簡單位圖所需位串的長度L（S）?。ㄇ褺LS－DEBI所需位串長度的最大值為靜態(tài)編碼位圖索引所需要的位串長度）。假設某數(shù)據(jù)表中元組總數(shù)為n，則若使用BLS－DEBI，整個數(shù)據(jù)表可以節(jié)省空間大于等于n（L（S）－L（B））；③隨著屬性基數(shù)值的增大，編碼位圖索引位串長度的變化率遠小于簡單位圖索引位串長度的變化率。

1．2 BLS－DEBI的使用范圍

假設某數(shù)據(jù)表中元組總數(shù)為n，現(xiàn)要為屬性F 建立索引。屬性F 共有m 種取值可能（即屬性F 的基數(shù)為m），磁盤每頁存儲數(shù)據(jù)量的大小為p，B＋樹的階數(shù)為m2。若要在該屬性上建立簡單位圖索引，則需要存儲空間；若建立B＋樹索引，則需要存儲空間若采用靜態(tài)編碼位圖索引，則需要存儲空間其中l(wèi)og2m表示每個編碼的長度；若采用BLS－DEBI所需要的存儲空間小于等于采用靜態(tài)編碼位圖索引所需要的存儲空間。將簡單位圖索引所需空間和編碼位圖索引所需空間比較得知，S3要遠小于S1，尤其是在數(shù)據(jù)量較大的情況下。

圖3 兩種位圖索引增長率的比較

現(xiàn)假設磁盤頁大小p＝4K，B＋樹的階數(shù)m2＝512，則計算出當n＞log2m ×m÷90時，B＋樹所需存儲空間比編碼位圖索引所需的存儲空間多。通常認為，需要使用編碼位圖建立索引的數(shù)據(jù)表，其元組數(shù)量n要遠大于m。

2 BLS－DEBI的創(chuàng)建

BLS－DEBI主要由兩部分構成，一部分是用于存儲實際屬性值和編碼值對應關系的映射表，另一部分是用于存儲索引編碼值和數(shù)據(jù)表記錄對應關系的鏈表。所以在創(chuàng)建BLS－DEBI時，需要對這兩部分都進行考慮。

例2：關于學生基本信息表的假設同例1。設現(xiàn)在共有5條元組信息，其中RId表示對應元組所在的行號RowId，E＿Sex、E＿Prov不是表中屬性，而是分別對性別和省份信息根據(jù)編碼位圖索引的規(guī)則生成的相應元組信息的編碼值?，F(xiàn)假設學生基本信息表如表1所示。

針對性別屬性列，若采用簡單位圖索引則可將性別為男和女分別編碼為0和1；針對省份屬性列可編碼為河北（00）、湖北（01）、山東（10）、北京（11）。

針對省份屬性信息建立的BLS－DEBI存儲結構如圖4所示。

表1 學生基本信息表

圖4 存儲省份屬性索引使用的雙向有序鏈表結構

3 BLS－DEBI的基本操作

3．1 元組插入

當有新數(shù)據(jù)需要插入時，首先遍歷已有的映射表，看該值是否已經(jīng)存在對應的編碼。若存在，則在編碼的對應節(jié)點中添加該條元組對應的RowId，否則計算編碼值的位數(shù)是否需要改變，如果不需要，則將插入數(shù)據(jù)對應的屬性值插入映射表并分配剩余的編碼值，否則需要為已編碼的值前面增加一位0，最后增加相應的數(shù)據(jù)項即可。

3．2 元組刪除

當刪除滿足給定條件的元組時，需要首先遍歷映射表以確認是否需要更新映射表中的元組信息。當映射表中除了被刪除元組的某屬性取值外，仍有其余元組在該屬性上的取值等于被刪除屬性值，則映射表只需刪除該元組的RowId，同時在數(shù)據(jù)表中刪除該元組信息即可。否則需要同時更新映射表和數(shù)據(jù)表。具體執(zhí)行流程如算法1所示。

算法1：編碼位圖索引情況下元組刪除算法。

輸入：用戶在某屬性F 上的查詢條件；

輸出：刪除是否成功的狀態(tài)值。

0－表示刪除失?。?/p>

1－表示刪除成功；

2－不存在滿足條件的刪除元組。

算法步驟：

Step1．數(shù)據(jù)表接收到刪除請求Con（F）；

Step2．在內存中查詢映射表，搜索Con（F）對應的編碼Ceb，若未查詢到滿足條件的元組值，直接返回2，表示不存在滿足條件的刪除元組信息，否則依次執(zhí)行Step3－8；

Step3．根據(jù)在Step2中生成的條件編碼位串Ceb按照相應的規(guī)則搜索雙向有序鏈表，返回對應節(jié)點記錄的所有滿足條件的RowId；

Step4．在映射表中刪除RowId信息；

Step5．如果對應鏈表節(jié)點值為空，同時刪除該鏈表節(jié)點，同時修改前后節(jié)點的指針指向；

Step6．檢查是否需要更新映射表，若需要同時更新編碼值；

Step7．根據(jù)Step3中獲得的RowId到數(shù)據(jù)表定位實際數(shù)據(jù)并刪除；

Step8．若Step7未出現(xiàn)異常信息，向用戶返回1，否則向用戶返回0。

3．3 元組更新

根據(jù)是否更新主鍵可以將元組更新操作分為兩類：一類是含主鍵屬性的更新。處理該類更新操作時，首先按照元組刪除的步驟執(zhí)行一次數(shù)據(jù)刪除，之后按照元組插入的步驟執(zhí)行一次數(shù)據(jù)插入，從而達到元組更新的目的。另一類是更新列不包含主鍵屬性的更新。該類更新又可以細分為更新屬性包含建立編碼位圖索引列和更新屬性不含已經(jīng)建立編碼位圖索引列。當更新屬性不包含已建立編碼位圖索引列時，直接依據(jù)元組的主鍵更新相應屬性值即可。當更新屬性包含建立編碼位圖索引的列時，首先需要根據(jù)刪除的相應操作更新映射表以及鏈表結構，然后根據(jù)插入的相應操作再次更新映射表和鏈表結構。

3．4 效率

從以上對數(shù)據(jù)的插入、刪除和更新的處理來看，由于位圖索引一般應用在屬性基數(shù)有限的情況下，而插入、刪除和更新操作只是相對于屬性的不同取值情況進行處理，所以編碼位圖索引處理時間可以看做與基數(shù)相關的一個常數(shù)，而與數(shù)據(jù)表中數(shù)據(jù)量的大小無關。

4 BLS－DEBI檢索算法

4．1 針對單個屬性上的檢索算法

在單個屬性上查詢時，首先根據(jù)用戶的查詢條件遍歷映射表，獲取查詢條件對應的編碼值。然后根據(jù)獲取的查詢條件編碼值在存儲索引的鏈表結構中用二分查找的算法通過二進制的邏輯異或運算，獲取滿足條件的元組標識信息。最后根據(jù)獲取的元組標識信息到數(shù)據(jù)表直接獲取用戶需要的信息。

算法2：針對單個屬性情況下的檢索算法。

輸入：用戶在某屬性F 上的查詢條件Con（F）；輸出：滿足用戶查詢條件的數(shù)據(jù)集。

算法步驟：

Step1．數(shù)據(jù)表接收到查詢請求Con（F）；

Step2．在內存中查詢映射表，搜索Con（F）對應的編碼Ceb，若沒有查詢到相應元組，則直接返回空集，否則依次執(zhí)行Step3－6；

Step3．根據(jù)在Step2中查詢到的條件編碼位圖Ceb按照相應的規(guī)則搜索有序鏈表結構；

Step4．返回鏈表中對應節(jié)點保存的所有滿足條件的RowIds；

Step5．根據(jù)Step4中返回的RowIds去數(shù)據(jù)表中定位元組的詳細信息；

Step6．將數(shù)據(jù)集返回給用戶。

4．2 針對多個屬性的檢索算法

在多個屬性上查詢時，首先將查詢條件分解成多個針對單個屬性的查詢條件，針對每個屬性依次執(zhí)行針對單個屬性情況下的檢索算法，最終得到的結果集即為滿足用戶要求的信息。

算法3：針對多個屬性情況下的檢索算法。

輸入：用戶在多個屬性上的查詢條件Con（F）；

輸出：滿足用戶查詢條件的數(shù)據(jù)集。

本實驗通過查閱文獻發(fā)現(xiàn)，豆蔻、白術的揮發(fā)性成分，丹參的脂溶性成分、水溶性酚酸類成分，大黃的蒽醌類化合物及其衍生物，炙甘草的三萜類、黃酮類和多糖類成分，山藥的多糖、氨基酸、微量元素等成分，均具有改善腎功能、調節(jié)胃腸功能、改善微循環(huán)、免疫調節(jié)和抗炎作用，因此，根據(jù)各味藥所含成分的水溶性及相關藥理作用，實驗設計了3種工藝路線，以此篩選JYP的最佳制備工藝。

算法步驟：

Step1．數(shù)據(jù)表接收到查詢請求Con（F）；

Step2．將查詢條件Con（F）進行分解，使每個Con（Fi）（0＜i＜n＋1，i默認值為1）對應數(shù)據(jù)表中已經(jīng)建立編碼位圖索引的一個屬性；

Step3．在內存中查詢映射表，搜索Con（Fi）對應的編碼Ceb，若沒有查詢到元組信息則直接向用戶返回空集，否則依次執(zhí)行Step4－6；

Step4．根據(jù)在Step3中生成的條件編碼位串Ceb按照二叉查找法搜索有序鏈表，通過邏輯運算判斷是否滿足查詢條件，獲取滿足條件的鏈表節(jié)點；

Step5．獲取鏈表對應節(jié)點中存儲的所有RowId；

Step6．如果i＝n則將最終獲取的數(shù)據(jù)集返回給用戶，否則i＝i＋1，返回繼續(xù)執(zhí)行Step3。

5 實驗分析

5．1 實驗環(huán)境

由于現(xiàn)有Oracle數(shù)據(jù)庫已經(jīng)集成B＋樹索引和基本位圖索引，所以本實驗是在一臺Windows Server操作系統(tǒng)、裝有Oracle 9i的PC 上完成的。本文算法是在Oracle存儲過程開發(fā)環(huán)境下實現(xiàn)、通過Microsoft Visual Studio 2010開發(fā)的Browser－Server程序調用測試的。

為了使實驗結果更具科學性，本實驗采取單一變量原則，主要包括以下幾組實驗：

（1）在12．8萬條數(shù)據(jù)情況下，分別采用全表掃描、B＋樹索引、簡單位圖索引、BLS－DEBI 4種算法進行檢索；

（2）在102．2萬條數(shù)據(jù)情況下，分別采用全表掃描、B＋樹索引、簡單位圖索引、BLS－DEBI 4種算法進行檢索；

（3）在1 000萬條數(shù)據(jù)情況下，分別采用全表掃描、B＋樹索引、簡單位圖索引、BLS－DEBI 4種算法進行檢索。

5．2 實驗結果對比分析

對比實驗是在3組相同數(shù)據(jù)量的情況下通過改變索引類型進行實現(xiàn)的。從表2可以看出，當數(shù)據(jù)量在10萬左右時采用B＋樹索引、簡單位圖索引和BLS－DEBI進行檢索時間不相上下，并且三者相對于直接遍歷數(shù)據(jù)表得到查詢結果的全表掃描，速度提升了近20多倍。從表2中可以看出，隨著數(shù)據(jù)量的增長，尤其是當數(shù)據(jù)集達到千萬級別時，采用B＋樹查詢所用的時間快速增長，而采用簡單位圖索引和BLSDEBI所用查詢時間增長較緩慢，從簡單位圖索引檢索時間和BLS－DEBI檢索時間數(shù)據(jù)可以清晰的看出：采用BLS－DEBI較簡單位圖索引更有優(yōu)勢。

表2 不同索引在不同數(shù)據(jù)量下檢索時間結果 ms

6 結語

在分析簡單位圖索引的優(yōu)勢和不足以及編碼位圖索引的優(yōu)勢的情況下，說明靜態(tài)編碼位圖索引以屬性基數(shù)對數(shù)的壓縮率減少了索引的存儲空間，而采用BLS－DEBI的方式，將進一步減少編碼位圖索引所需要的位串長度，并通過數(shù)學函數(shù)的形式直觀的體現(xiàn)出編碼索引的壓縮率。同時由于采用雙向有序鏈表的索引存儲結構加快了數(shù)據(jù)檢索的效率，并節(jié)省了存儲索引所需空間。最后通過實驗證明BLS－DEBI較B＋樹索引、簡單位圖索引在數(shù)據(jù)檢索方面具有一定的優(yōu)勢。

［1］孟必平，王騰蛟，李紅燕，等．分片位圖索引：一種適用于云數(shù)據(jù)管理的輔助索引機制［J］．計算機學報，2012，35（11）：2306－2316．

［2］Ni Z，Guo J，Wang L，et al．An efficient method for improving query efficiency in data warehouse［J］．Journal of Software（1796217X），2011，6（5）：857－865．

［3］Wu Y，Shou L D，Chen G．CB－LSH：An efficient LSH indexing algorithm based on compressed bitmap［J］．Journal of Zhejiang University．Engineering Science，2012，46（3）：376－385．

［4］Lu P，Wu S，Shou L，et al．An efficient and compact indexing scheme for large－scale data store［C］／／Data Engineering（ICDE），IEEE Computer Society Washington，DC，USA ?2005，2013 IEEE29th International Conference on．IEEE．［S．l．］：［s．n．］，2013：326－337．

［5］Lemire D，Kaser O，Aouiche K．Sorting improves word－aligned bitmap indexes［J］．Data ＆ Knowledge Engineering，2010，69（1）：3－28．

［6］Wen Y，Chen M，Lu G，et al．A characteristic bitmap coding method for vector elements based on self－adaptive gridding［J］．International Journal of Geographical Information Science，2013，27（10）：1939－1959．

［7］郭歡，葉小平，湯庸，等．基于時態(tài)編碼和線序劃分的時態(tài)XML 索引［J］．軟件學報，2012，23（8）：2042－2057．

［8］Bin H，Yuxing P．An efficient two－level bitmap index for cloud data management［C］／／Communication Software and Networks（ICCSN），IEEE Computer Society Washington，DC，USA ?2005，2011 IEEE3rd International Conference on．IEEE．［S．l．］：［s．n．］，2011：509－513．

［9］胡廷波，鐘?。诜执氐腂＋樹數(shù)據(jù)庫索引優(yōu)化算法［J］．計算機應用，2013，33（9）：2474－2476．