王書(shū)海， 劉桂蘭， 綦朝暉

（1．石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院，河北 石家莊 050043；（2．河北省大型結(jié)構(gòu)健康診斷與控制實(shí)驗(yàn)室，河北 石家莊 050043）

0 引言

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

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

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

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

從圖1可以看出，使用B＋樹(shù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，不僅需要存儲(chǔ)所有數(shù)據(jù)節(jié)點(diǎn)，同時(shí)增加了標(biāo)識(shí)數(shù)據(jù)最值的邊節(jié)點(diǎn)。

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

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

1．1 基本原理

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

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

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

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

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

圖2 存儲(chǔ)省份屬性使用的雙向有序鏈表結(jié)構(gòu)

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

1．2 BLS－DEBI的使用范圍

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

圖3 兩種位圖索引增長(zhǎng)率的比較

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

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

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

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

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

針對(duì)省份屬性信息建立的BLS－DEBI存儲(chǔ)結(jié)構(gòu)如圖4所示。

表1 學(xué)生基本信息表

圖4 存儲(chǔ)省份屬性索引使用的雙向有序鏈表結(jié)構(gòu)

3 BLS－DEBI的基本操作

3．1 元組插入

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

3．2 元組刪除

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

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

輸入：用戶(hù)在某屬性F 上的查詢(xún)條件；

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

0－表示刪除失??；

1－表示刪除成功；

2－不存在滿(mǎn)足條件的刪除元組。

算法步驟：

Step1．?dāng)?shù)據(jù)表接收到刪除請(qǐng)求Con（F）；

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

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

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

Step5．如果對(duì)應(yīng)鏈表節(jié)點(diǎn)值為空，同時(shí)刪除該鏈表節(jié)點(diǎn)，同時(shí)修改前后節(jié)點(diǎn)的指針指向；

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

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

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

3．3 元組更新

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

3．4 效率

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

4 BLS－DEBI檢索算法

4．1 針對(duì)單個(gè)屬性上的檢索算法

在單個(gè)屬性上查詢(xún)時(shí)，首先根據(jù)用戶(hù)的查詢(xún)條件遍歷映射表，獲取查詢(xún)條件對(duì)應(yīng)的編碼值。然后根據(jù)獲取的查詢(xún)條件編碼值在存儲(chǔ)索引的鏈表結(jié)構(gòu)中用二分查找的算法通過(guò)二進(jìn)制的邏輯異或運(yùn)算，獲取滿(mǎn)足條件的元組標(biāo)識(shí)信息。最后根據(jù)獲取的元組標(biāo)識(shí)信息到數(shù)據(jù)表直接獲取用戶(hù)需要的信息。

算法2：針對(duì)單個(gè)屬性情況下的檢索算法。

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

算法步驟：

Step1．?dāng)?shù)據(jù)表接收到查詢(xún)請(qǐng)求Con（F）；

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

Step3．根據(jù)在Step2中查詢(xún)到的條件編碼位圖Ceb按照相應(yīng)的規(guī)則搜索有序鏈表結(jié)構(gòu)；

Step4．返回鏈表中對(duì)應(yīng)節(jié)點(diǎn)保存的所有滿(mǎn)足條件的RowIds；

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

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

4．2 針對(duì)多個(gè)屬性的檢索算法

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

算法3：針對(duì)多個(gè)屬性情況下的檢索算法。

輸入：用戶(hù)在多個(gè)屬性上的查詢(xún)條件Con（F）；

輸出：滿(mǎn)足用戶(hù)查詢(xún)條件的數(shù)據(jù)集。

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

算法步驟：

Step1．?dāng)?shù)據(jù)表接收到查詢(xún)請(qǐng)求Con（F）；

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

Step3．在內(nèi)存中查詢(xún)映射表，搜索Con（Fi）對(duì)應(yīng)的編碼Ceb，若沒(méi)有查詢(xún)到元組信息則直接向用戶(hù)返回空集，否則依次執(zhí)行Step4－6；

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

Step5．獲取鏈表對(duì)應(yīng)節(jié)點(diǎn)中存儲(chǔ)的所有RowId；

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

5 實(shí)驗(yàn)分析

5．1 實(shí)驗(yàn)環(huán)境

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

為了使實(shí)驗(yàn)結(jié)果更具科學(xué)性，本實(shí)驗(yàn)采取單一變量原則，主要包括以下幾組實(shí)驗(yàn)：

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

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

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

5．2 實(shí)驗(yàn)結(jié)果對(duì)比分析

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

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

6 結(jié)語(yǔ)

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

［1］孟必平，王騰蛟，李紅燕，等．分片位圖索引：一種適用于云數(shù)據(jù)管理的輔助索引機(jī)制［J］．計(jì)算機(jī)學(xué)報(bào)，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］郭歡，葉小平，湯庸，等．基于時(shí)態(tài)編碼和線(xiàn)序劃分的時(shí)態(tài)XML 索引［J］．軟件學(xué)報(bào)，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ù)數(shù)據(jù)庫(kù)索引優(yōu)化算法［J］．計(jì)算機(jī)應(yīng)用，2013，33（9）：2474－2476．