內(nèi)存數(shù)據(jù)庫中的索引技術(shù)

wang290

引言　　傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)把所有數(shù)據(jù)都放在磁盤上進行管理，所以稱作磁盤數(shù)據(jù)庫（DRDB: Disk-Resident Database）。磁盤數(shù)據(jù)庫需要頻繁地訪問磁盤來進行數(shù)據(jù)的操作，磁盤的讀寫速度遠遠小于CPU處理數(shù)據(jù)的速度，所以磁盤數(shù)據(jù)庫的瓶頸出現(xiàn)在磁盤讀寫上。
　　基于此，內(nèi)存數(shù)據(jù)庫的概念被提出來了。內(nèi)存數(shù)據(jù)庫(MMDB:Main Memory Database，也叫主存數(shù)據(jù)庫)[1]，就是將數(shù)據(jù)全部或者大部分放在內(nèi)存中進行操作的數(shù)據(jù)庫管理系統(tǒng)，對查詢處理、并發(fā)控制與恢復(fù)的算法和數(shù)據(jù)結(jié)構(gòu)進行重新設(shè)計，以更有效地使用CPU周期和內(nèi)存。相對于磁盤，內(nèi)存的數(shù)據(jù)讀寫速度要高出幾個數(shù)量級，將數(shù)據(jù)保存在內(nèi)存中相比從磁盤上訪問能夠極大地提高應(yīng)用的性能。
　　近十幾年來，內(nèi)存的發(fā)展一直遵循摩爾定律[2]，內(nèi)存的價格一直下降，而內(nèi)存的容量一直在增加�，F(xiàn)在的主流服務(wù)器，幾百GB或者幾TB的內(nèi)存都很常見，內(nèi)存的發(fā)展使得內(nèi)存數(shù)據(jù)庫得以實現(xiàn)。
　　由于內(nèi)存數(shù)據(jù)庫與傳統(tǒng)的磁盤數(shù)據(jù)庫在設(shè)計和架構(gòu)上都大不相同，所以傳統(tǒng)的數(shù)據(jù)庫索引不適用于內(nèi)存數(shù)據(jù)庫。研究者為改進內(nèi)存數(shù)據(jù)庫的索引結(jié)構(gòu)做了相當(dāng)多的研究跟工作。其中，影響較大的索引有早期的T樹、基于緩存敏感(cacheconscious)的CSS/CSB+樹，Trie-tree和Hash等等。本文就這幾種有代表性的索引算法進行研究和分析，為進一步改進內(nèi)存數(shù)據(jù)庫索引算法和提高索引性能打下堅實的基礎(chǔ)。
　　2、T-tree
　　2.1 T-tree
　　T-tree是針對主存訪問優(yōu)化的索引技術(shù)[3]。T-tree是一種一個節(jié)點中包含多個索引條目的平衡二叉樹，T-tree的索引項無論是從大小還是算法上都比B-tree精簡得多。T-tree的搜索算法不分搜索的值在當(dāng)前的節(jié)點還是在內(nèi)存中的其他地方，每訪問到一個新的索引節(jié)點，索引的范圍減少一半。

圖2-1T-Tree的結(jié)點

　　T-tree索引用來實現(xiàn)關(guān)鍵字的范圍查詢。T-tree是一棵特殊平衡的二叉樹（AVL），它的每個節(jié)點存儲了按鍵值排序的一組關(guān)鍵字。T-tree除了較高的節(jié)點空間占有率，遍歷一棵樹的查找算法在復(fù)雜程度和執(zhí)行時間上也占有優(yōu)勢�，F(xiàn)在T-tree己經(jīng)成為內(nèi)存數(shù)據(jù)庫中最主要的一種索引方式。
　　T-tree具有以下特點：1）左子樹與右子樹之差不超過1，2）在一個存儲節(jié)點可以保存多個鍵值，它的最左與最右鍵值分別為這個節(jié)點的最小與最大鍵值，它的左子樹僅僅包含那些鍵值小于或等于最小鍵值的一記錄，同理右子樹只包括那些鍵值大于或等于最大鍵值的記錄，3）同時擁有左右子樹的節(jié)點被稱為內(nèi)部節(jié)點，只擁有一個子樹的節(jié)點被稱為半葉節(jié)點，沒有子樹的節(jié)點被稱為葉子，4）為了保持空間的利用率，每一個內(nèi)部節(jié)點都需要包含一個最小數(shù)目的鍵值。由此可知T-tree是一個每個結(jié)點含有多個關(guān)鍵字的平衡二叉樹，每個節(jié)點內(nèi)的關(guān)鍵字有序排列，左子樹都要比根節(jié)點關(guān)鍵字小，右子樹都要比根節(jié)點關(guān)鍵字大。
　　在上述T-tree結(jié)點結(jié)構(gòu)中，包含如下信息:
　　(1)balance(平衡因子)，其絕對值不大于1，balance=右子樹高度-左子樹高度；
　　(2)Left_child_ptr和Right_child_ptr分別表示當(dāng)前結(jié)點的左子樹和右子樹指針；
　　(3)Max_Item表示結(jié)點中所能容納的鍵值的最大數(shù)；
　　(4)Key[0]至K[Max_Item-1]為結(jié)點內(nèi)存放的關(guān)鍵字；
　　(5)nItem是當(dāng)前節(jié)點實際存儲的關(guān)鍵字個數(shù)。
　　對于T-tree有如下特征：
　　(1)與AVL樹相似，T-tree中任何結(jié)點的左右子樹的高度之差最大為1；
　　(2)與AVL樹不同，T-tree的結(jié)點中可存儲多個鍵值，并且這些鍵值排列有序；
　　(3)T-tree結(jié)點的左子樹中容納的鍵值不大于該結(jié)點中的最左鍵值；右子樹中容納的鍵值不小于該結(jié)點中的最右鍵值；
　　(4)為了保證每個結(jié)點具有較高的空間占用率，每個內(nèi)部結(jié)點所包含的鍵值數(shù)目必須不小于某個指定的值，通常為(Max_Item-2)(Max_Item為結(jié)點中最大鍵值目)。
　　2.2 T-tree索引的操作
　　用T-tree作為索引方式主要完成三個工作：查找，插入，刪除。其中插入和刪除都是以查找為基礎(chǔ)。下面分別介紹三種操作的流程。
　　2.2.1 查找
　　T-tree的查找類似于二叉樹，不同之處主要在于每一結(jié)點上的比較不是針對結(jié)點中的各個元素值，而是首先檢查所要查找的目標(biāo)鍵值是否包含在當(dāng)前結(jié)點的最左鍵值和最右鍵值所確定的范圍內(nèi)，如果是的話，則在當(dāng)前結(jié)點的鍵值列表中使用二分法進行查找；如果目標(biāo)鍵值小于當(dāng)前結(jié)點的最左鍵值，則類似地搜索當(dāng)前結(jié)點的左孩子結(jié)點；如果目標(biāo)鍵值大于當(dāng)前結(jié)點的最右鍵值，則類似地搜索當(dāng)前結(jié)點的右孩子結(jié)點。
　　2. 2.2 插入
　　T-tree的插入是以查找為基礎(chǔ)，應(yīng)用查找操作定位目標(biāo)鍵值插入位置，并記下查找過程所遇到的最后結(jié)點。如果查找成功，判斷此結(jié)點中是否有足夠的存儲空間。如果有，則將目標(biāo)鍵值插入結(jié)點中；否則將目標(biāo)鍵值插入此結(jié)點，然后將結(jié)點中的最左鍵值插入到它的左子樹中(此時是遞歸插入操作)，之后結(jié)束；否則分配新結(jié)點，并插入目標(biāo)鍵值；然后根據(jù)目標(biāo)鍵值與結(jié)點的最大最小鍵值之間的關(guān)系，將新分配的結(jié)點鏈接為結(jié)點的左孩子或右孩子；對樹進行檢查，判斷T-tree的平衡因子是否滿足條件，如果平衡因子不滿足則執(zhí)行旋轉(zhuǎn)操作。
　　2.2.3 刪除
　　T-tree的刪除操作也是以查找為基礎(chǔ)，應(yīng)用查找操作定位目標(biāo)鍵值。如果查找失敗，則結(jié)束；否則令N為目標(biāo)鍵值所在的結(jié)點，并從結(jié)點N中刪除目標(biāo)鍵值；刪除節(jié)點后，如果結(jié)點N為空，則刪除結(jié)點N，并對樹的平衡因子進行檢查，判斷是否需要執(zhí)行旋轉(zhuǎn)操作；如果結(jié)點N中的鍵值數(shù)量少于最小值，則根據(jù)N的平衡因子決定從結(jié)點N的左子樹中移出最大的鍵值或者右子樹中移出最小值來填充。
　　2.3 T-tree索引實現(xiàn)關(guān)鍵技術(shù)
　　實現(xiàn)T-tree索引即要實現(xiàn)T-tree的查找，插入和刪除。其中又以查找為基礎(chǔ)，對T-tree的維護也就是T-tree的旋轉(zhuǎn)為關(guān)鍵。當(dāng)由于插入或刪除鍵值導(dǎo)致樹的失衡，則要進行T-tree的旋轉(zhuǎn)。使之重新達到平衡。
　　在插入情況下，需要依次對所有沿著從新創(chuàng)建結(jié)點到根結(jié)點路徑中的結(jié)點進行檢查，直到出現(xiàn)如下兩種情況之一時中止：某個被檢查結(jié)點的兩個子樹高度相等，此時不需要執(zhí)行旋轉(zhuǎn)操作；某個被檢查結(jié)點的兩個子樹的高度之差大于1，此時對該結(jié)點僅需執(zhí)行一次旋轉(zhuǎn)操作即可。
　　在刪除情況下，類似地需要依次對所有沿著從待刪除結(jié)點的父結(jié)點到根結(jié)點路徑中的結(jié)點進行檢查，在檢查過程中當(dāng)發(fā)現(xiàn)某個結(jié)點的左右子樹高度之差越界時，需要執(zhí)行一次旋轉(zhuǎn)操作。與插入操作不同的是，執(zhí)行完旋轉(zhuǎn)操作之后，檢查過程不能中止，而是必須一直執(zhí)行到檢查完根結(jié)點。
　　由此可以看出，對于插入操作，最多只需要一次旋轉(zhuǎn)操作即可使T-tree恢復(fù)到平衡狀態(tài)；而對于刪除操作則可能會引起向上的連鎖反應(yīng)，使高層結(jié)點發(fā)生旋轉(zhuǎn)，因而可能需要進行多次旋轉(zhuǎn)操作。
　　為了對T-tree進行平衡，需要進行旋轉(zhuǎn)操作，旋轉(zhuǎn)是T-tree中最關(guān)鍵也是最難的的操作，下面介紹T-tree旋轉(zhuǎn)的技術(shù)。旋轉(zhuǎn)可分為四種情況：由左孩子的左子樹的插入（或者刪除）引起的旋轉(zhuǎn)記為LL旋轉(zhuǎn)，類似有LR，RR及RL旋轉(zhuǎn)。插入時的情況與刪除類似。
　　3、CSS/CSB+樹
　　3.1 CSS-trees
　　3.1.1 Introduction
　　CSS-trees(Cache-SensitiveSearch Trees),可以提供比二分查找更為迅速的查詢操作而又不需大量額外的空間[4]。該技術(shù)在在一個以排好序的數(shù)組頂端存儲一個目錄結(jié)構(gòu)，且該目錄結(jié)構(gòu)的節(jié)點大小與機器cache-line大小相匹配。將該目錄結(jié)構(gòu)存儲在數(shù)組中而無需存儲內(nèi)部節(jié)點的指針，子節(jié)點可通過數(shù)組偏移量定位，這與B+-trees不同。
　　3.2 FULL CSS-Tree
　　構(gòu)造一棵結(jié)點包含m個鍵值的查詢樹，樹的深度是d，那么一直到d-1的深度這棵樹是一棵完全(m+1)-查詢樹，而在d層葉子結(jié)點從左往右分布。一棵m=4的實例樹圖3-1所示，其中方塊數(shù)就是結(jié)點數(shù)，且每個結(jié)點有四個鍵值。

　　CSS-Tree的結(jié)點可以存儲在數(shù)組中，如圖3-2所示：
　　3.2.1 構(gòu)造FULL CSS-Tree
　　將一個已排好序的數(shù)組構(gòu)造一棵相應(yīng)的Full CSS-Tree，首先將數(shù)組分為兩部分，并且在葉子節(jié)點和數(shù)組元素間建立匹配。然后從最后一個內(nèi)部節(jié)點開始，將節(jié)點直接左子樹的最大鍵值作為節(jié)點入口。對于某一些內(nèi)部節(jié)點，也就是最深層最后一個葉子節(jié)點的祖先，可能完全鍵值，可以用數(shù)組前半部分最后的一個元素來填充這些鍵值，所以在某些內(nèi)部節(jié)點會有一些復(fù)制的鍵值。盡管要增量更新一棵Full CSS-Tree樹是很困難的，但構(gòu)造這樣一棵樹花費并不大。實驗表明對于有著兩千五百萬鍵值的數(shù)組，構(gòu)造其相應(yīng)的Full CSS-Tree花費的時間不足一秒。
　　3.2.2 查詢Full CSS-Tree
　　從根節(jié)點開始，每次都查詢一個內(nèi)部節(jié)點，利用二分查找來決定查找哪一個分支，重復(fù)上述行為直到葉子節(jié)點，最后將葉子節(jié)點與排好序的數(shù)組進行匹配。
　　在節(jié)點內(nèi)所有的查詢都由if-else構(gòu)成，在內(nèi)部節(jié)點進行二分查找時，一直比較左邊的鍵值是否不小于要查詢的鍵值，當(dāng)找到第一個比要查詢的鍵值小時，停止比較并進入右邊的分支（如果找不到這樣的值，就進入最左邊的分支）。這樣可以保證當(dāng)在節(jié)點中有復(fù)制的值時，我們可以在所有復(fù)制的鍵值中找到最左邊的鍵值。
　　3.3 LevelCSS-Tree
　　對于每個節(jié)點有m個記錄的Full CSS-Tree，有嚴(yán)格的m個鍵值，所有的記錄都會被利用到。對于m=2t，我們定義每個節(jié)點只有只有m-1條記錄，并且有一個分支因子m。一棵Level CSS-Tree樹比一棵相應(yīng)的Full CSS-Tree樹的深度大，因為分支因子是m而不是m+1，然后對于每一個節(jié)點，需要的同伴數(shù)更少。若N為一個已排好序的數(shù)組元素所對應(yīng)的節(jié)點數(shù)，Level CSS-Tree有l(wèi)ogmN層，而Full CSS-Tree有l(wèi)ogm+1N層。每個節(jié)點的同伴數(shù)是t，而Full CSS-tree是t*(1+2/(m+1))，所以Level CSS-tree的總的同伴數(shù)是logmN*t=log2N,而Full CSS-tree是logm+1N*t*(1+2/(m+1))=log2N*logm+1m*(1+2(m+1)).因此，Level CSS-Tree所需的companion數(shù)比Full CSS-tree少。另一方面，Level CSS-Tree需要logmN個cache accesses，遍歷logmN個節(jié)點，而Full CSS-Tree需logm+1N。
　　構(gòu)建一棵Level CSS-Tree與Full CSS-Tree類似，我們也可以利用每個節(jié)點的空槽，來存儲最后一個分支的最大值，來避免遍歷整棵子樹來獲取最大元素值。查詢一棵Level CSS-Tree也與查詢Full CSS-Tree類似，唯一的不同就是子節(jié)點偏移量的計算。
　　3.4 CSB+-Tree
　　3.4.1 Introduction
　　盡管CSS-Tree相比二分查找和T-Trees查詢性能更好，但是它是用于決策支持的有著相對靜態(tài)數(shù)據(jù)的工作負(fù)載設(shè)計的。CSB+-Tree(CacheSensitive B+-Trees)[4],是B+-Trees的變體，連續(xù)存儲給定節(jié)點的子節(jié)點，并且只存儲節(jié)點的第一個子節(jié)點的地址，其他子節(jié)點的地址可以通過相對這個子節(jié)點的偏移量計算獲得。由于只存儲一個子節(jié)點的指針，cache的利用率是很高的，與B+-Tree類似，CSB+-Tree支持增量更新。
　　CSB+-Tree有兩種變體，分段CSB+-Tree(SegmentedCSB+-tree)和完全CSB+-tree(FullCSB+-Tree).分段CSB+-Tree將子節(jié)點分段，在同一段的子節(jié)點連續(xù)存儲，在每個節(jié)點中，只有每一段的起始地址才會被存儲。當(dāng)有分裂時，分段CSB+-Tree可以減少復(fù)制開銷，因為只有一個分段需要移動。完全CSB+-Tree為整個節(jié)點重新分配空間，因此減少了分裂開銷。
　　3.4.2 CSB+-Tree上的操作
　　1）  Bulkload.
　　對于CSB+-Tree樹，一個有效的bulkload方法就是一層一層的建立索引結(jié)構(gòu)。為每一個葉節(jié)點分配空間，計算在高層需要的節(jié)點數(shù)，并給該層分配連續(xù)的存儲空間。通過將低層每一個節(jié)點的最大值填入高層的節(jié)點，并設(shè)置每一個高層節(jié)點的第一個子節(jié)點指針。重復(fù)上述操作直到高層只有一個節(jié)點，且這個節(jié)點為根節(jié)點。因為同一層的所有節(jié)點是連續(xù)的，所以構(gòu)造節(jié)點組無需額外的復(fù)制操作。
　　2）  Search
　　查詢CSB+-Tree與查詢B+-Tree類似，當(dāng)最右邊節(jié)點的鍵值K比要查詢的鍵值小，給第一個子節(jié)點增加K的偏移量來獲得子節(jié)點的地址。例如，K是節(jié)點的第三個鍵值，可以用一個c語句找到子節(jié)點：child=first_child+3，其中child和first_child是節(jié)點的指針。
　　3）  Insertion
　　對CSB+-Tree的插入操作也與B+-Tree類似，首先要查找鍵值的插入口，一旦定位至相應(yīng)葉節(jié)點，判斷該葉節(jié)點是否有足夠的空間，如果有，就簡單的將鍵值放置在該葉節(jié)點中，否則，需要分裂該葉節(jié)點。
　　當(dāng)需要分裂葉節(jié)點時，基于父節(jié)點是否有足夠的空間存放鍵值會產(chǎn)生兩種情況。假設(shè)父節(jié)點p有足夠的空間，令f為p的第一個子節(jié)點的指針，g為f指向的節(jié)點組，構(gòu)建一個新的比g多了一個節(jié)點的節(jié)點組g’，將g中所有的節(jié)點復(fù)制到g’，g中要分裂的節(jié)點在g’中變?yōu)閮蓚�節(jié)點，更新p中第一個子節(jié)點的指針f，使它指向g’，并且重新分配g。
　　當(dāng)父節(jié)點沒有額外的空間并且自身需要分裂時，問題顯得更為復(fù)雜。令f為p中第一個節(jié)點的指針，需要構(gòu)建新的節(jié)點組g’，將g中的節(jié)點均分至g’和g中，p中一半的鍵值轉(zhuǎn)移至g’中。為了將p分裂為p和p’，包含p的節(jié)點組需要像第一種情況一樣進行復(fù)制，或者，如果節(jié)點組也是滿的，我們需要遞歸的分裂p的父節(jié)點。父節(jié)點再重復(fù)上述操作。
　　4）Deletion
　　刪除操作類似于插入操作，一般的，簡單的定位數(shù)據(jù)入口并且加以刪除。無需調(diào)整樹保證50%的occupancy[5]
　　3.4.3 Segmented CSB+-Tree
　　考慮128字節(jié)的cache-line，CSB+-Tree中每個節(jié)點最多有30個鍵值，意味著每個節(jié)點可以有31個子節(jié)點，那么一個節(jié)點組最大可達31*128近4KB，因此每一個分裂，需要復(fù)制4KB的數(shù)據(jù)來創(chuàng)建一個節(jié)點組，若cache-line更大，分裂一個節(jié)點的開銷將會更大。
　　修改節(jié)點結(jié)構(gòu)可以減少分裂時的復(fù)制操作�？梢詫⒆庸�(jié)點分段，將每一段的地址存儲在節(jié)點中，每一段形成了一個節(jié)點組，只有在同一段的子節(jié)點被連續(xù)存儲。第一種考慮是固定每一個分段的大小，填充第一個分段的節(jié)點，一旦第一個分段滿了，就將節(jié)點放在第二個分段。若一個節(jié)點落在第二個分段，我們只需將第二個分段的節(jié)點復(fù)制到新的段中，而無需管第一個分段，若新的節(jié)點落在第一個分段(已經(jīng)滿了)，我們需要將數(shù)據(jù)從第一個分段移至第二個分段，在上述例子中，針對隨機插入，分裂產(chǎn)生的數(shù)據(jù)復(fù)制將會減少至1/2(1/2+3/4)*4KB=2.5KB.另一種就是允許每個分段的大小不同，最終將節(jié)點分為兩段。當(dāng)有節(jié)點插入時，為這個節(jié)點所屬的分段創(chuàng)建一個新的分段，并更新相應(yīng)分段的大小。在這種方法中，嚴(yán)格來說每次插入只涉及到一個分段(但當(dāng)父節(jié)點也需要分裂，此時兩個分段都要復(fù)制)，若一個新的節(jié)點等可能的落入其中一個分段，一個分裂產(chǎn)生的數(shù)據(jù)復(fù)制量為1/2*4KB=2KB，這種方法可以進一步的減少數(shù)據(jù)復(fù)制量。有兩個分段的SegmentedCSB+Tree如圖3-3所示(每個葉節(jié)點只有兩個鍵值)：

　　分段CSB+-Tree可支持所有對樹的操作，方法與非分段CSB+-Tree類似，然而，查找每個節(jié)點的右孩子比起非分段的CSB+-Tree的開銷大，因為需要找到孩子所在的分段。
　　3.4.4 FULLCSB+-Tree
　　在FULLCSB+-Tree中，節(jié)點分裂的開銷比CSB+-Tree小。在CSB+-Tree中，當(dāng)節(jié)點分裂時，需要將節(jié)點組整個復(fù)制到新的組中，而在FullCSB+-Tree中，只需訪問節(jié)點組的一半。對于這種轉(zhuǎn)移操作的源地址和目的地址有大的交叉，訪問的cache-line的數(shù)目限制在s內(nèi)。FULLCSB+-Tree在分裂上的平均時間開銷是0.5s，而CSB+-Tree需時2s。
　　3.5 時間空間分析
　　假定鍵值、子節(jié)點指針、元組ID有著相同的空間大小K，n為葉節(jié)點數(shù)，c為cache-line的字節(jié)數(shù)，t為分段CSB+-Tree的分段數(shù)。每個節(jié)點的槽值為m，其中m=c/K，假定節(jié)點大小與cache-line相同，各個參數(shù)及其相應(yīng)的值如圖3-4所示：
　　圖3-5顯示了各種方法間分支因子、鍵值差異數(shù)、cache未命中數(shù)、每個節(jié)點其他差異的比較。B+-Tree的分支因子比CSS-Tree小，而CSB+-Tree存儲的子節(jié)點指針少，所需的分支因子與CSS-Tree相近。這導(dǎo)致每個方法的cache未命中次數(shù)不一樣。節(jié)點的分支因子越大，cache未命中次數(shù)相應(yīng)的越小。在CSB+-Tree每增加一個分段，分支因子就會減少2，這是由于需要一個槽來存儲子節(jié)點指針，另一個槽來存儲新增分段的大小。一般而言，B+-Tree中節(jié)點的70%空間是滿的，需要相應(yīng)的調(diào)整分支因子大小。[6]

圖 3-5  CSB+-Tree查詢時間分析

　　圖3-6顯示了在分裂時預(yù)期要訪問的cache-line數(shù)。由于復(fù)制時源地址和目的地址有交叉，所以FullCSB+-Tree所需的數(shù)目小。分裂開銷是插入操作總開銷的一部分，另一部分是定位優(yōu)葉子節(jié)點產(chǎn)生的查詢開銷。分裂開銷相對獨立于樹的深度，這是由于大多數(shù)的分裂都發(fā)生在葉節(jié)點。然而，當(dāng)樹的規(guī)模越來越大時，相應(yīng)的查詢產(chǎn)生的開銷也會增大。CSB+-Tree的分裂開銷比B+-Tree大，但是插入產(chǎn)生的總開銷還與樹的規(guī)模有關(guān)。

　　圖3-7 顯示了不同算法的空間需求。假定所有節(jié)點70%的空間是滿的[6]，且分別計算內(nèi)部節(jié)點和葉節(jié)點的空間大小，假定每個葉節(jié)點有2個兄弟節(jié)點指針。內(nèi)部節(jié)點空間大小等于葉節(jié)點空間乘以1/(q-1)(q為分支因子),這里不比較CSS-Tree，因為CSS-Tree不可能部分滿。


　　4    Trie-tree索引　　4.1 Trie-tree　　Trie-Tree[7]又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
　　4.1.1 Trie-tree性質(zhì)　　它有三個基本的性質(zhì)：
　　1）根節(jié)點不包含字符，除根節(jié)點以外每一個節(jié)點都只包含一個字符
　　2）從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的的字符連接起來，為改節(jié)點對應(yīng)的字符串。
　　3）每個節(jié)點的所有子節(jié)點包含的字符都不相同。
　　圖4-1 展示了一個基本的tire-tree結(jié)構(gòu)

　　圖4-1 tire-tree

　　4.1.2 Trie樹的基本實現(xiàn)　　字母樹的插入、刪除和查找都非常簡單，用一個一重循環(huán)即可，即第i次循環(huán)找到前i個字母所對應(yīng)的子樹，然后進行相應(yīng)的操作。實現(xiàn)這棵字母樹，我們用最常見的數(shù)組保存（靜態(tài)開辟內(nèi)存）即可，當(dāng)然也可以開動態(tài)的指針類型（動態(tài)開辟內(nèi)存）。至于結(jié)點對兒子的指向，一般有三種方法：
　　1）對每個結(jié)點開一個字母集大小的數(shù)組，對應(yīng)的下標(biāo)是兒子所表示的字母，內(nèi)容則是這個兒子對應(yīng)在大數(shù)組上的位置，即標(biāo)號；
　　2）對每個結(jié)點掛一個鏈表，按一定順序記錄每個兒子是誰；
　　3）使用左兒子右兄弟表示法記錄這棵樹。
　　三種方法，各有特點。第一種易實現(xiàn)，但實際的空間要求較大；第二種，較易實現(xiàn)，空間要求相對較小，但比較費時；第三種，空間要求最小，但相對費時且不易寫。
　　4.1.2.1 實現(xiàn)方法　　搜索字典[8]項目的方法為：
　　1) 從根結(jié)點開始一次搜索；
　　2) 取得要查找關(guān)鍵詞的第一個字母，并根據(jù)該字母選擇對應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進行檢索；
　　3) 在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個字母,并進一步選擇對應(yīng)的子樹進行檢索。
　　4) 迭代過程……
　　5) 在某個結(jié)點處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點上的信息，即完成查找。
　　其他操作類似處理
　　4.1.2.2 Trie原理　　Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
　　4.1.3 Trie樹的高級實現(xiàn)Double-Array 實現(xiàn)　　可以采用雙數(shù)組（Double-Array）實現(xiàn),如圖1.3。利用雙數(shù)組可以大大減小內(nèi)存使用量，具體實現(xiàn)
　　兩個數(shù)組，一個是base[]，另一個是check[]。設(shè)數(shù)組下標(biāo)為i，如果base, check均為0，表示該位置為空。如果base為負(fù)值，表示該狀態(tài)為終止態(tài)（即詞語）。check表示該狀態(tài)的前一狀態(tài)。
　　定義 1. 對于輸入字符 c,從狀態(tài) s 轉(zhuǎn)移到狀態(tài) t,雙數(shù)組字典樹滿足如下條件(圖4-2):

check[base + c] = s

base + c = t

　　從定義1中，我們能得到查找算法，對于給定的狀態(tài) s 和輸入字符 c ：
t := base + c;if check[t] = s then    next state := telse    failendif
　　我們知道雙數(shù)組的實現(xiàn)方法是當(dāng)狀態(tài)有新轉(zhuǎn)移時才分配空間給新狀態(tài)，或可以表述為只分配需要轉(zhuǎn)移的狀態(tài)的空間。當(dāng)遇到無法滿足上述條件時再進行調(diào)整，使得其 base 值滿足上述條件，這種調(diào)整只影響當(dāng)前節(jié)點下一層節(jié)點的重分配，因為所有節(jié)點的地址分配是靠 base 數(shù)組指定的起始下標(biāo)所決定的。插入的操作，假設(shè)以某字符開頭的 base 值為i，第二個字符的字符序列碼依次為c1, c2, c3…cn，則肯定要滿足base[i+c1], check[i+c1], base[i+c2], check[i+c2], base[i+c3], check[i+c3]…base[i+cn],check[i+cn]均為0。

圖4-3 Double Array 實現(xiàn)

　　假設(shè)，Tire里有n個節(jié)點，字符集大小為m，則DATrie的空間大小是n+cm，c是依賴于Trie稀疏程度的一個系數(shù)。而多路查找樹的空間大小是nm。
　　注意，這里的復(fù)雜度都是按離線算法（offline algorithm）計算的，即處理時已經(jīng)得到整個詞庫。在線算法（online algorithm）的空間復(fù)雜度還和單詞出現(xiàn)的順序有關(guān)，越有序的單詞順序空間占用越小。
　　查找算法的復(fù)雜度和被查找的字符串長度相關(guān)的，這個復(fù)雜度和多路查找樹是一樣的。
　　插入算法中，如果出現(xiàn)重分配的情況，我們要附加上掃描子節(jié)點的時間復(fù)雜度，還有新base值確定的算法復(fù)雜度。假如這兒我們都是用暴力算法（for循環(huán)掃描），那插入算法時間復(fù)雜度是O(nm + cm2)。。
　　實際編碼過程中，DATrie代碼難度大過多路查找樹，主要是狀態(tài)的表示不如樹結(jié)構(gòu)那樣的清晰，下標(biāo)很容易搞混掉。
　　有個地方需要注意的是，base值正數(shù)表示起始偏移量，負(fù)數(shù)表示該狀態(tài)為終止態(tài)，所以在查找新base值時，要保證查到的值是正數(shù)。
如：空Trie狀態(tài)下，插入d時，因為第一個空地址是1，所以得到base=1-4=-3，這樣base正負(fù)的含義就被**了。
　　4.1.4 Trie樹的應(yīng)用　　Trie是一種非常簡單高效的數(shù)據(jù)結(jié)構(gòu)，但有大量的應(yīng)用實例。
　�。�1）字符串檢索
　　事先將已知的一些字符串（字典）的有關(guān)信息保存到trie樹里，查找另外一些未知字符串是否出現(xiàn)過或者出現(xiàn)頻率。例如：
　　1）給出N個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現(xiàn)的順序?qū)懗鏊�有不在熟詞表中的生詞。
　　2）給出一個詞典，其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本，文本的每一行也由小寫字母構(gòu)成。判斷文本中是否含有任何不良單詞。例如，若rob是不良單詞，那么文本problem含有不良單詞。
　�。�2）字符串最長公共前綴
　　Trie樹利用多個字符串的公共前綴來節(jié)省存儲空間，反之，當(dāng)我們把大量字符串存儲到一棵trie樹上時，我們可以快速得到某些字符串的公共前綴。
　　例如：給出N個小寫英文字母串，以及Q個詢問，即詢問某兩個串的最長公共前綴的長度是多少？
　　解決方案：首先對所有的串建立其對應(yīng)的字母樹。此時發(fā)現(xiàn)，對于兩個串的最長公共前綴的長度即它們所在結(jié)點的公共祖先個數(shù)，于是，問題就轉(zhuǎn)化為了離線（Offline）的最近公共祖先（LeastCommon Ancestor，簡稱LCA）問題。
　　而最近公共祖先問題同樣是一個經(jīng)典問題，可以用下面幾種方法：
　　1）利用并查集（Disjoint Set），可以采用采用經(jīng)典的Tarjan算法；
　　2）求出字母樹的歐拉序列（Euler Sequence）后，就可以轉(zhuǎn)為經(jīng)典的最小值查詢（Range Minimum Query，簡稱RMQ）問題
　�。�3）排序
　　Trie樹是一棵多叉樹，只要先序遍歷整棵樹，輸出相應(yīng)的字符串便是按字典序排序的結(jié)果。例如：給你N個互不相同的僅由一個單詞構(gòu)成的英文名，讓你將它們按字典序從小到大排序輸出。
　�。�4）作為其他數(shù)據(jù)結(jié)構(gòu)和算法的輔助結(jié)構(gòu)，如后綴樹，AC自動機等
　　4.1.5 Trie樹復(fù)雜度分析　�。�1）插入、查找的時間復(fù)雜度均為O(N)，其中N為字符串長度。
　　（2）空間復(fù)雜度是26^n級別的，非常龐大（可采用雙數(shù)組實現(xiàn)改善）。
　　4.1.6 總結(jié)　　Trie樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，它在信息檢索，字符串匹配等領(lǐng)域有廣泛的應(yīng)用，同時，它也是很多算法和復(fù)雜數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，如后綴樹，AC自動機等。
　　4.2 TrieMemory　　Trie Memory[9]是一種在內(nèi)存中存儲和檢索信息的方式，這種方式的優(yōu)點是訪問速度快，具有冗余存儲信息的優(yōu)點，主要的缺點是存儲空間利用率很低。
　　4.2.1 基本的Trie Memory模型　　假設(shè)我們需要跟蹤一系列的單詞集合，這些集合是字母組成的序列。這些單詞序列有各種各樣的長度，我們必須記住的是這些字母組成的有限序列在這個集合中�？偟脕碚f，我們需要判斷一個序列是不是這個集合的成員。
　　剛開始trie僅僅是register組成的一個集合，除此之外還有兩個register，一個是α另一個是δ，每一個register都有cell來存儲整個字母表，如果我們要存儲“space”的話，每個register必須擁有27個cell。
每一個cell都有空間來存儲其它register在內(nèi)存中的地址，trie中的cell還沒有用來存儲信息，通常包含的是register α的地址信息。一個cell如果包含了非register α的register地址，則它表示存儲了信息，這些信息代表了這個cell的名稱，“A”表示A cell,“B”表示B cell。下一個register的地址在序列中。
　　下面用一個例子(圖2.1)來說明，為了讓例子簡單些，我們使用字母表的前5個字符來表示整體。然后用▽表示“space”，假設(shè)我們想存儲DAB,BAD,BADE,BE,BED,BEAD,CAB,CAD和A，接下來用圖來說明整個流程。在圖中每一行代表一個register，每個register有6個cell,最后一行代表第三個特殊的register叫做portal register,是我們進入系統(tǒng)內(nèi)存的通道它除了是入口外，也和其它register是一樣的。其它register是編號的。register α將會選擇它們。剛開始的時候 register α是register 2。

圖4-4 基本Tire Memory模型

　　為了存儲DAB，我們引入地址“2”進入portal register的D 單元格，然后我們移動到register 2然后引入地址“3”到A單元格，然后我們進入到register 3后把地址“4”放入單元格B，最后我們移動到register 4 并且把地址“1”放入▽單元，它是終止參數(shù)，至此DAB存儲結(jié)束。然后我們轉(zhuǎn)到第二個單詞BAD，引入地址“5”進入portal register的B單元格來表示字母B，然后到register 5的A單元格寫入地址“6”，再到register 6的D單元格寫入地址“7”，最后到register 7的▽單元格寫入地址“1”。當(dāng)我們開始存儲BADE時，我們發(fā)現(xiàn)B,A,D已經(jīng)在trie中了，因此我們沿著已經(jīng)存在的BAD的路徑到register 7然后引入地址“8”到單元格E中去，然后把地址“1”放入register 8的▽單元。
　　4.2.2 Register的類型
　　在剛才提到的結(jié)構(gòu)中我們可以把register分為4種類型：
　　1）α(address) register來指向下一個存儲信息的地址
　　2）δ(deletion) register
　　3）ν(next) register，下一步將要存儲的信息(在空內(nèi)存中，它是portal register)
　　4）χ(exterior)類型χ是所有register中還沒有接受存儲信息并且沒有被指向為下一個存儲位置的register。
　　5）ο(occupied)類型ο是存有信息的register
　　4.2.3 Trie的讀和寫　　在上述的所有的register中除了χ都在trie中，存儲和讀取操作現(xiàn)在能夠被簡單的公平的定義如下。
　　4.2.3.1 寫操作　　1）把第i個參數(shù)字符傳入下一個register，如果是第一個字符，則是portal register
　　2）選擇對應(yīng)字符串的的cell,如果第i個參數(shù)字符是字母表的第j個字符，選擇第j個cell。
　　3）檢測來自第i個單元的聯(lián)結(jié)
　　4）如果這種聯(lián)結(jié)使得register α：
　　a） 通過αregister把聯(lián)結(jié)投射到鏈接的頭部，這樣就可以存儲信息。
　　b)投射從αregister到鏈接頭部的聯(lián)結(jié)來創(chuàng)建一個“next”register(ν)
　　c)最后，把所有的從ν發(fā)出來的聯(lián)結(jié)指向αregister。
　　5）如果源于第j個cell的聯(lián)結(jié)指向非 αregister的話，移動到那個register去：
　　a） 如果是第一個register，這參數(shù)是一個存儲集合的成員(結(jié)束流程)。
　　b）如果不是register 1的話，i加1并且轉(zhuǎn)到第二步去。
　　4.2.3.2 讀操作　　使用相同的流程，但是不要使用投射，不要投射任何關(guān)系，如果聯(lián)結(jié)指向register 1，則這個參數(shù)是存儲集合的一個成員，如果任何點的聯(lián)結(jié)指向αregister,換句話說這個參數(shù)不是存儲集合的成員。
　　5 HASH索引
　　HASH就是把關(guān)鍵詞直接映射為存儲地址，達到快速尋址的目的，即Addr=H(key)，其中key為關(guān)鍵詞；H為哈希函數(shù)。主要有以下幾種常用的哈希函數(shù)：
　　1)除留余數(shù)法(DivisionMethod)，H(key)=keyMOD p，p一般為質(zhì)數(shù)；
　　2)隨機數(shù)法(RandomMethod)，H(key)=random(key)，random為隨機函數(shù)；
　　3)平方取中法(MidsquareMethod)。
　　HASH索引結(jié)構(gòu)不需要額外的存儲空間，并且能夠在O(1)的時間復(fù)雜度下準(zhǔn)確定位到所查找的數(shù)據(jù)，將磁盤數(shù)據(jù)庫中的數(shù)據(jù)查找時間代價優(yōu)化至最小。Hash索引結(jié)構(gòu)由于以上優(yōu)點在磁盤數(shù)據(jù)庫中廣泛的運用。經(jīng)歷長久的研究，先后發(fā)展出了鏈接桶哈希(chainedbucket hash)[10]，可擴展哈希(extendible hash)[11]、線性哈希(linearhash)[12]和修正的線性哈希(modified linear hash)[13]。但是這些哈希算法雖然針對內(nèi)存數(shù)據(jù)庫進行了少許優(yōu)化，但是與傳統(tǒng)數(shù)據(jù)庫中所用的哈希算法沒有明顯不同。到了2007年，KennethA. Ross提出了基于現(xiàn)代處理器的Hash預(yù)取算法[14]將SIMD指令集融入到Hash算法中，才真正從內(nèi)存索引的角度改進了哈希算法，提升數(shù)據(jù)組織的效率。
　　5.1 鏈接桶哈希
　　鏈接桶哈希（圖5-1）是一個靜態(tài)的結(jié)構(gòu)，可用于內(nèi)存中與磁盤中。因為它是靜態(tài)結(jié)構(gòu)，不用對數(shù)據(jù)進行重組織，所以它速度很快。但這也是它的缺陷，面對動態(tài)數(shù)據(jù)，就顯得不合適了，因為鏈接桶哈希必須在使用之前知道哈希表的大小，而這恰恰很難預(yù)測。如果預(yù)測的表大小過小，其性能會大受影響；如果過大，空間浪費較為嚴(yán)重。最好情況下，它只有一些空間的浪費，用來存放指向下一個桶的指針。

　　5.2 可擴展哈希

　　可擴展哈希（圖5-2）引入了目錄文件的概念，采用可隨數(shù)據(jù)增長的動態(tài)哈希表，因此克服了鏈接桶哈希的缺陷，其哈希表大小不需要預(yù)先知道，一個哈希節(jié)點包含多個項，當(dāng)節(jié)點數(shù)量溢出時將其分裂為兩個節(jié)點。目錄按2的指數(shù)倍增長，當(dāng)一個節(jié)點裝滿而且到達了一個特定的目錄大小目錄就會倍增。哈希函數(shù)為每個鍵計算一個K位的二進制序列，桶的數(shù)量總是使用從序列第一位或者最后一位算起的若干位[]。但是可擴展哈希的一個問題是任意一個節(jié)點都會引起目錄的分裂，當(dāng)哈希函數(shù)不夠隨機時，目錄很可能增長的很巨大。

　　5.3 線性哈希
　　線性哈希（圖5-3）也使用動態(tài)的哈希表，但是同可擴展哈希有較大差別。線性哈希選擇桶數(shù)總是使存儲塊的平均記錄保持與容量成一個固定的比例。而且哈希桶不總是可以分裂，允許有溢出塊。當(dāng)插入的記錄沒有對應(yīng)的桶，將其哈希值首位改為0，再次插入，否則直接插入對應(yīng)桶或其溢出塊中。當(dāng)記錄數(shù)量比容量達到一個閾值，增加一個桶，再分配。相對于可擴展哈希，線性哈希的增長較為緩慢，重組織的次數(shù)和代價都較小。同時，線性散列不需要存放數(shù)據(jù)桶指針的專門目錄項，且能更自然的處理數(shù)據(jù)桶已滿的情況，允許更靈活的選擇桶分裂的時機。

　　5.4 修正的線性哈希
　　修正的線性哈希相對于線性哈希主要面向內(nèi)存環(huán)境。通過使用更大的連續(xù)節(jié)點替代目錄，普通的線性哈希由于有空節(jié)點而浪費空間。而且，除非有一個巧妙的方案解決潛在的虛擬內(nèi)存映射機制問題，不然每次目錄增長時那個連續(xù)的節(jié)點都要被拷貝到一個更大的內(nèi)存塊。修正的線性哈希采用跟可擴展哈希一樣的目錄，除了目錄為線性增長的，鏈接的是單個項目的節(jié)點和分配內(nèi)存是從一個常規(guī)的內(nèi)存池。這個算法節(jié)點分裂的準(zhǔn)則是基于性能，舉例來說，監(jiān)控哈希鏈的平均長度比監(jiān)控存儲利用率能夠更直接的控制平均搜索和更新時間[13]。
　　5.5 Hash預(yù)取算法
　　Hash預(yù)取算法面向的是鍵和哈希值都是32位的場景，特地對內(nèi)存環(huán)境進行了優(yōu)化。此算法使用乘法散列，這種方法十分普遍、計算高效，更重要的是適用于矢量，達到了一次計算多個哈希函數(shù)的目的[14]。針對現(xiàn)代處理器的SIMD架構(gòu)，將鍵值與哈希值共同放在一個指令當(dāng)中，達到大大減少指令數(shù)的目的，令每次所需的數(shù)據(jù)長度恰好等于L2的cacheline，大大降低了性能代價，在內(nèi)存環(huán)境中，大大提高了cache的性能。

lanyuflying

這個內(nèi)容很好，怎么沒人頂

wang290

lanyuflying 發(fā)表于 2015-02-05 14:48
這個內(nèi)容很好，怎么沒人頂

感謝支持！

流氓無產(chǎn)者

高大尚啊

renxiao2003

和關(guān)系數(shù)據(jù)庫的技術(shù)基本上同出一轍。

cjfeii

贊一個