引言

　　傳統的數據庫管理系統把所有數據都放在磁盤上進行管理，所以稱作磁盤數據庫（DRDB: Disk-Resident Database）。磁盤數據庫需要頻繁地訪問磁盤來進行數據的操作，磁盤的讀寫速度遠遠小于CPU處理數據的速度，所以磁盤數據庫的瓶頸出現在磁盤讀寫上。

　　基于此，內存數據庫的概念被提出來了。內存數據庫(MMDB:Main Memory Database，也叫主存數據庫)^[1]，就是將數據全部或者大部分放在內存中進行操作的數據庫管理系統，對查詢處理、并發控制與恢復的算法和數據結構進行重新設計，以更有效地使用CPU周期和內存。相對于磁盤，內存的數據讀寫速度要高出幾個數量級，將數據保存在內存中相比從磁盤上訪問能夠極大地提高應用的性能。

　　近十幾年來，內存的發展一直遵循摩爾定律^[2]，內存的價格一直下降，而內存的容量一直在增加。現在的主流服務器，幾百GB或者幾TB的內存都很常見，內存的發展使得內存數據庫得以實現。

　　由于內存數據庫與傳統的磁盤數據庫在設計和架構上都大不相同，所以傳統的數據庫索引不適用于內存數據庫。研究者為改進內存數據庫的索引結構做了相當多的研究跟工作。其中，影響較大的索引有早期的T樹、基于緩存敏感(cacheconscious)的CSS/CSB+樹，Trie-tree和Hash等等。本文就這幾種有代表性的索引算法進行研究和分析，為進一步改進內存數據庫索引算法和提高索引性能打下堅實的基礎。

　　2、T-tree

　　2.1 T-tree

　　T-tree是針對主存訪問優化的索引技術^[3]。T-tree是一種一個節點中包含多個索引條目的平衡二叉樹，T-tree的索引項無論是從大小還是算法上都比B-tree精簡得多。T-tree的搜索算法不分搜索的值在當前的節點還是在內存中的其他地方，每訪問到一個新的索引節點，索引的范圍減少一半。

圖2-1T-Tree的結點

　　T-tree索引用來實現關鍵字的范圍查詢。T-tree是一棵特殊平衡的二叉樹（AVL），它的每個節點存儲了按鍵值排序的一組關鍵字。T-tree除了較高的節點空間占有率，遍歷一棵樹的查找算法在復雜程度和執行時間上也占有優勢。現在T-tree己經成為內存數據庫中最主要的一種索引方式。

　　T-tree具有以下特點：1）左子樹與右子樹之差不超過1，2）在一個存儲節點可以保存多個鍵值，它的最左與最右鍵值分別為這個節點的最小與最大鍵值，它的左子樹僅僅包含那些鍵值小于或等于最小鍵值的一記錄，同理右子樹只包括那些鍵值大于或等于最大鍵值的記錄，3）同時擁有左右子樹的節點被稱為內部節點，只擁有一個子樹的節點被稱為半葉節點，沒有子樹的節點被稱為葉子，4）為了保持空間的利用率，每一個內部節點都需要包含一個最小數目的鍵值。由此可知T-tree是一個每個結點含有多個關鍵字的平衡二叉樹，每個節點內的關鍵字有序排列，左子樹都要比根節點關鍵字小，右子樹都要比根節點關鍵字大。

　　在上述T-tree結點結構中，包含如下信息:

　　(1)balance(平衡因子)，其絕對值不大于1，balance=右子樹高度-左子樹高度；

　　(2)Left_child_ptr和Right_child_ptr分別表示當前結點的左子樹和右子樹指針；

　　(3)Max_Item表示結點中所能容納的鍵值的最大數；

　　(4)Key[0]至K[Max_Item-1]為結點內存放的關鍵字；

　　(5)nItem是當前節點實際存儲的關鍵字個數。

　　對于T-tree有如下特征：

　　(1)與AVL樹相似，T-tree中任何結點的左右子樹的高度之差最大為1；

　　(2)與AVL樹不同，T-tree的結點中可存儲多個鍵值，并且這些鍵值排列有序；

　　(3)T-tree結點的左子樹中容納的鍵值不大于該結點中的最左鍵值；右子樹中容納的鍵值不小于該結點中的最右鍵值；

　　(4)為了保證每個結點具有較高的空間占用率，每個內部結點所包含的鍵值數目必須不小于某個指定的值，通常為(Max_Item-2)(Max_Item為結點中最大鍵值目)。

　　2.2 T-tree索引的操作

　　用T-tree作為索引方式主要完成三個工作：查找，插入，刪除。其中插入和刪除都是以查找為基礎。下面分別介紹三種操作的流程。

　　2.2.1 查找

　　T-tree的查找類似于二叉樹，不同之處主要在于每一結點上的比較不是針對結點中的各個元素值，而是首先檢查所要查找的目標鍵值是否包含在當前結點的最左鍵值和最右鍵值所確定的范圍內，如果是的話，則在當前結點的鍵值列表中使用二分法進行查找；如果目標鍵值小于當前結點的最左鍵值，則類似地搜索當前結點的左孩子結點；如果目標鍵值大于當前結點的最右鍵值，則類似地搜索當前結點的右孩子結點。

　　2. 2.2 插入

　　T-tree的插入是以查找為基礎，應用查找操作定位目標鍵值插入位置，并記下查找過程所遇到的最后結點。如果查找成功，判斷此結點中是否有足夠的存儲空間。如果有，則將目標鍵值插入結點中；否則將目標鍵值插入此結點，然后將結點中的最左鍵值插入到它的左子樹中(此時是遞歸插入操作)，之后結束；否則分配新結點，并插入目標鍵值；然后根據目標鍵值與結點的最大最小鍵值之間的關系，將新分配的結點鏈接為結點的左孩子或右孩子；對樹進行檢查，判斷T-tree的平衡因子是否滿足條件，如果平衡因子不滿足則執行旋轉操作。

　　2.2.3 刪除

　　T-tree的刪除操作也是以查找為基礎，應用查找操作定位目標鍵值。如果查找失敗，則結束；否則令N為目標鍵值所在的結點，并從結點N中刪除目標鍵值；刪除節點后，如果結點N為空，則刪除結點N，并對樹的平衡因子進行檢查，判斷是否需要執行旋轉操作；如果結點N中的鍵值數量少于最小值，則根據N的平衡因子決定從結點N的左子樹中移出最大的鍵值或者右子樹中移出最小值來填充。

　　2.3 T-tree索引實現關鍵技術

　　實現T-tree索引即要實現T-tree的查找，插入和刪除。其中又以查找為基礎，對T-tree的維護也就是T-tree的旋轉為關鍵。當由于插入或刪除鍵值導致樹的失衡，則要進行T-tree的旋轉。使之重新達到平衡。

　　在插入情況下，需要依次對所有沿著從新創建結點到根結點路徑中的結點進行檢查，直到出現如下兩種情況之一時中止：某個被檢查結點的兩個子樹高度相等，此時不需要執行旋轉操作；某個被檢查結點的兩個子樹的高度之差大于1，此時對該結點僅需執行一次旋轉操作即可。

　　在刪除情況下，類似地需要依次對所有沿著從待刪除結點的父結點到根結點路徑中的結點進行檢查，在檢查過程中當發現某個結點的左右子樹高度之差越界時，需要執行一次旋轉操作。與插入操作不同的是，執行完旋轉操作之后，檢查過程不能中止，而是必須一直執行到檢查完根結點。

　　由此可以看出，對于插入操作，最多只需要一次旋轉操作即可使T-tree恢復到平衡狀態；而對于刪除操作則可能會引起向上的連鎖反應，使高層結點發生旋轉，因而可能需要進行多次旋轉操作。

　　為了對T-tree進行平衡，需要進行旋轉操作，旋轉是T-tree中最關鍵也是最難的的操作，下面介紹T-tree旋轉的技術。旋轉可分為四種情況：由左孩子的左子樹的插入（或者刪除）引起的旋轉記為LL旋轉，類似有LR，RR及RL旋轉。插入時的情況與刪除類似。

　　3、CSS/CSB+樹

　　3.1 CSS-trees

　　3.1.1 Introduction

　　CSS-trees(Cache-SensitiveSearch Trees),可以提供比二分查找更為迅速的查詢操作而又不需大量額外的空間^[4]。該技術在在一個以排好序的數組頂端存儲一個目錄結構，且該目錄結構的節點大小與機器cache-line大小相匹配。將該目錄結構存儲在數組中而無需存儲內部節點的指針，子節點可通過數組偏移量定位，這與B+-trees不同。

　　3.2 FULL CSS-Tree

　　構造一棵結點包含m個鍵值的查詢樹，樹的深度是d，那么一直到d-1的深度這棵樹是一棵完全(m+1)-查詢樹，而在d層葉子結點從左往右分布。一棵m=4的實例樹圖3-1所示，其中方塊數就是結點數，且每個結點有四個鍵值。

　　CSS-Tree的結點可以存儲在數組中，如圖3-2所示：

　　3.2.1 構造FULL CSS-Tree

　　將一個已排好序的數組構造一棵相應的Full CSS-Tree，首先將數組分為兩部分，并且在葉子節點和數組元素間建立匹配。然后從最后一個內部節點開始，將節點直接左子樹的最大鍵值作為節點入口。對于某一些內部節點，也就是最深層最后一個葉子節點的祖先，可能完全鍵值，可以用數組前半部分最后的一個元素來填充這些鍵值，所以在某些內部節點會有一些復制的鍵值。盡管要增量更新一棵Full CSS-Tree樹是很困難的，但構造這樣一棵樹花費并不大。實驗表明對于有著兩千五百萬鍵值的數組，構造其相應的Full CSS-Tree花費的時間不足一秒。

　　3.2.2 查詢Full CSS-Tree

　　從根節點開始，每次都查詢一個內部節點，利用二分查找來決定查找哪一個分支，重復上述行為直到葉子節點，最后將葉子節點與排好序的數組進行匹配。

　　在節點內所有的查詢都由if-else構成，在內部節點進行二分查找時，一直比較左邊的鍵值是否不小于要查詢的鍵值，當找到第一個比要查詢的鍵值小時，停止比較并進入右邊的分支（如果找不到這樣的值，就進入最左邊的分支）。這樣可以保證當在節點中有復制的值時，我們可以在所有復制的鍵值中找到最左邊的鍵值。

　　3.3 LevelCSS-Tree

　　對于每個節點有m個記錄的Full CSS-Tree，有嚴格的m個鍵值，所有的記錄都會被利用到。對于m=2^t，我們定義每個節點只有只有m-1條記錄，并且有一個分支因子m。一棵Level CSS-Tree樹比一棵相應的Full CSS-Tree樹的深度大，因為分支因子是m而不是m+1，然后對于每一個節點，需要的同伴數更少。若N為一個已排好序的數組元素所對應的節點數，Level CSS-Tree有log_mN層，而Full CSS-Tree有log_m+1N層。每個節點的同伴數是t，而Full CSS-tree是t*(1+2/(m+1))，所以Level CSS-tree的總的同伴數是log_mN*t=log₂N,而Full CSS-tree是log_m+1N*t*(1+2/(m+1))=log₂N*log_m+1m*(1+2(m+1)).因此，Level CSS-Tree所需的companion數比Full CSS-tree少。另一方面，Level CSS-Tree需要log_mN個cache accesses，遍歷log_mN個節點，而Full CSS-Tree需log_m+1N。

　　構建一棵Level CSS-Tree與Full CSS-Tree類似，我們也可以利用每個節點的空槽，來存儲最后一個分支的最大值，來避免遍歷整棵子樹來獲取最大元素值。查詢一棵Level CSS-Tree也與查詢Full CSS-Tree類似，唯一的不同就是子節點偏移量的計算。

　　3.4 CSB+-Tree

　　3.4.1 Introduction

　　盡管CSS-Tree相比二分查找和T-Trees查詢性能更好，但是它是用于決策支持的有著相對靜態數據的工作負載設計的。CSB+-Tree(CacheSensitive B+-Trees)^[4],是B+-Trees的變體，連續存儲給定節點的子節點，并且只存儲節點的第一個子節點的地址，其他子節點的地址可以通過相對這個子節點的偏移量計算獲得。由于只存儲一個子節點的指針，cache的利用率是很高的，與B+-Tree類似，CSB+-Tree支持增量更新。

　　CSB+-Tree有兩種變體，分段CSB+-Tree(SegmentedCSB+-tree)和完全CSB+-tree(FullCSB+-Tree).分段CSB+-Tree將子節點分段，在同一段的子節點連續存儲，在每個節點中，只有每一段的起始地址才會被存儲。當有分裂時，分段CSB+-Tree可以減少復制開銷，因為只有一個分段需要移動。完全CSB+-Tree為整個節點重新分配空間，因此減少了分裂開銷。

　　3.4.2 CSB+-Tree上的操作

　　1）  Bulkload.

　　對于CSB+-Tree樹，一個有效的bulkload方法就是一層一層的建立索引結構。為每一個葉節點分配空間，計算在高層需要的節點數，并給該層分配連續的存儲空間。通過將低層每一個節點的最大值填入高層的節點，并設置每一個高層節點的第一個子節點指針。重復上述操作直到高層只有一個節點，且這個節點為根節點。因為同一層的所有節點是連續的，所以構造節點組無需額外的復制操作。

　　2）  Search

　　查詢CSB+-Tree與查詢B+-Tree類似，當最右邊節點的鍵值K比要查詢的鍵值小，給第一個子節點增加K的偏移量來獲得子節點的地址。例如，K是節點的第三個鍵值，可以用一個c語句找到子節點：child=first_child+3，其中child和first_child是節點的指針。

　　3）  Insertion

　　對CSB+-Tree的插入操作也與B+-Tree類似，首先要查找鍵值的插入口，一旦定位至相應葉節點，判斷該葉節點是否有足夠的空間，如果有，就簡單的將鍵值放置在該葉節點中，否則，需要分裂該葉節點。

　　當需要分裂葉節點時，基于父節點是否有足夠的空間存放鍵值會產生兩種情況。假設父節點p有足夠的空間，令f為p的第一個子節點的指針，g為f指向的節點組，構建一個新的比g多了一個節點的節點組g’，將g中所有的節點復制到g’，g中要分裂的節點在g’中變為兩個節點，更新p中第一個子節點的指針f，使它指向g’，并且重新分配g。

　　當父節點沒有額外的空間并且自身需要分裂時，問題顯得更為復雜。令f為p中第一個節點的指針，需要構建新的節點組g’，將g中的節點均分至g’和g中，p中一半的鍵值轉移至g’中。為了將p分裂為p和p’，包含p的節點組需要像第一種情況一樣進行復制，或者，如果節點組也是滿的，我們需要遞歸的分裂p的父節點。父節點再重復上述操作。

　　4）Deletion

　　刪除操作類似于插入操作，一般的，簡單的定位數據入口并且加以刪除。無需調整樹保證50%的occupancy^[5]

　　3.4.3 Segmented CSB+-Tree

　　考慮128字節的cache-line，CSB+-Tree中每個節點最多有30個鍵值，意味著每個節點可以有31個子節點，那么一個節點組最大可達31*128近4KB，因此每一個分裂，需要復制4KB的數據來創建一個節點組，若cache-line更大，分裂一個節點的開銷將會更大。

　　修改節點結構可以減少分裂時的復制操作。可以將子節點分段，將每一段的地址存儲在節點中，每一段形成了一個節點組，只有在同一段的子節點被連續存儲。第一種考慮是固定每一個分段的大小，填充第一個分段的節點，一旦第一個分段滿了，就將節點放在第二個分段。若一個節點落在第二個分段，我們只需將第二個分段的節點復制到新的段中，而無需管第一個分段，若新的節點落在第一個分段(已經滿了)，我們需要將數據從第一個分段移至第二個分段，在上述例子中，針對隨機插入，分裂產生的數據復制將會減少至1/2(1/2+3/4)*4KB=2.5KB.另一種就是允許每個分段的大小不同，最終將節點分為兩段。當有節點插入時，為這個節點所屬的分段創建一個新的分段，并更新相應分段的大小。在這種方法中，嚴格來說每次插入只涉及到一個分段(但當父節點也需要分裂，此時兩個分段都要復制)，若一個新的節點等可能的落入其中一個分段，一個分裂產生的數據復制量為1/2*4KB=2KB，這種方法可以進一步的減少數據復制量。有兩個分段的SegmentedCSB+Tree如圖3-3所示(每個葉節點只有兩個鍵值)：

　　分段CSB+-Tree可支持所有對樹的操作，方法與非分段CSB+-Tree類似，然而，查找每個節點的右孩子比起非分段的CSB+-Tree的開銷大，因為需要找到孩子所在的分段。

　　3.4.4 FULLCSB+-Tree

　　在FULLCSB+-Tree中，節點分裂的開銷比CSB+-Tree小。在CSB+-Tree中，當節點分裂時，需要將節點組整個復制到新的組中，而在FullCSB+-Tree中，只需訪問節點組的一半。對于這種轉移操作的源地址和目的地址有大的交叉，訪問的cache-line的數目限制在s內。FULLCSB+-Tree在分裂上的平均時間開銷是0.5s，而CSB+-Tree需時2s。

　　3.5 時間空間分析

　　假定鍵值、子節點指針、元組ID有著相同的空間大小K，n為葉節點數，c為cache-line的字節數，t為分段CSB+-Tree的分段數。每個節點的槽值為m，其中m=c/K，假定節點大小與cache-line相同，各個參數及其相應的值如圖3-4所示：

　　圖3-5顯示了各種方法間分支因子、鍵值差異數、cache未命中數、每個節點其他差異的比較。B+-Tree的分支因子比CSS-Tree小，而CSB+-Tree存儲的子節點指針少，所需的分支因子與CSS-Tree相近。這導致每個方法的cache未命中次數不一樣。節點的分支因子越大，cache未命中次數相應的越小。在CSB+-Tree每增加一個分段，分支因子就會減少2，這是由于需要一個槽來存儲子節點指針，另一個槽來存儲新增分段的大小。一般而言，B+-Tree中節點的70%空間是滿的，需要相應的調整分支因子大小。^[6]

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

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

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

　　4    Trie-tree索引

　　4.1 Trie-tree

　　Trie-Tree^[7]又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。 

　　4.1.1 Trie-tree性質

　　它有三個基本的性質：

　　1）根節點不包含字符，除根節點以外每一個節點都只包含一個字符

　　2）從根節點到某一節點，路徑上經過的的字符連接起來，為改節點對應的字符串。

　　3）每個節點的所有子節點包含的字符都不相同。

　　圖4-1 展示了一個基本的tire-tree結構

　　圖4-1 tire-tree

　　4.1.2 Trie樹的基本實現

　　字母樹的插入、刪除和查找都非常簡單，用一個一重循環即可，即第i次循環找到前i個字母所對應的子樹，然后進行相應的操作。實現這棵字母樹，我們用最常見的數組保存（靜態開辟內存）即可，當然也可以開動態的指針類型（動態開辟內存）。至于結點對兒子的指向，一般有三種方法：

　　1）對每個結點開一個字母集大小的數組，對應的下標是兒子所表示的字母，內容則是這個兒子對應在大數組上的位置，即標號；

　　2）對每個結點掛一個鏈表，按一定順序記錄每個兒子是誰；

　　3）使用左兒子右兄弟表示法記錄這棵樹。

　　三種方法，各有特點。第一種易實現，但實際的空間要求較大；第二種，較易實現，空間要求相對較小，但比較費時；第三種，空間要求最小，但相對費時且不易寫。

　　4.1.2.1 實現方法

　　搜索字典^[8]項目的方法為：

　　1) 從根結點開始一次搜索；

　　2) 取得要查找關鍵詞的第一個字母，并根據該字母選擇對應的子樹并轉到該子樹繼續進行檢索；

　　3) 在相應的子樹上，取得要查找關鍵詞的第二個字母,并進一步選擇對應的子樹進行檢索。

　　4) 迭代過程……

　　5) 在某個結點處，關鍵詞的所有字母已被取出，則讀取附在該結點上的信息，即完成查找。

　　其他操作類似處理

　　4.1.2.2 Trie原理

　　Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。

　　4.1.3 Trie樹的高級實現Double-Array 實現

　　可以采用雙數組（Double-Array）實現,如圖1.3。利用雙數組可以大大減小內存使用量，具體實現

　　兩個數組，一個是base[]，另一個是check[]。設數組下標為i，如果base[i], check[i]均為0，表示該位置為空。如果base[i]為負值，表示該狀態為終止態（即詞語）。check[i]表示該狀態的前一狀態。

　　定義 1. 對于輸入字符 c,從狀態 s 轉移到狀態 t,雙數組字典樹滿足如下條件(圖4-2):

　　從定義1中，我們能得到查找算法，對于給定的狀態 s 和輸入字符 c ：

t := base[s] + c;
if check[t] = s then
    next state := t
else
    fail
endif

　　我們知道雙數組的實現方法是當狀態有新轉移時才分配空間給新狀態，或可以表述為只分配需要轉移的狀態的空間。當遇到無法滿足上述條件時再進行調整，使得其 base 值滿足上述條件，這種調整只影響當前節點下一層節點的重分配，因為所有節點的地址分配是靠 base 數組指定的起始下標所決定的。插入的操作，假設以某字符開頭的 base 值為i，第二個字符的字符序列碼依次為c₁, c₂, c₃…c_n，則肯定要滿足base[i+c₁], check[i+c₁], base[i+c₂], check[i+c₂], base[i+c₃], check[i+c₃]…base[i+c_n],check[i+c_n]均為0。

圖4-3 Double Array 實現

　　假設，Tire里有n個節點，字符集大小為m，則DATrie的空間大小是n+cm，c是依賴于Trie稀疏程度的一個系數。而多路查找樹的空間大小是nm。
　　注意，這里的復雜度都是按離線算法（offline algorithm）計算的，即處理時已經得到整個詞庫。在線算法（online algorithm）的空間復雜度還和單詞出現的順序有關，越有序的單詞順序空間占用越小。
　　查找算法的復雜度和被查找的字符串長度相關的，這個復雜度和多路查找樹是一樣的。
　　插入算法中，如果出現重分配的情況，我們要附加上掃描子節點的時間復雜度，還有新base值確定的算法復雜度。假如這兒我們都是用暴力算法（for循環掃描），那插入算法時間復雜度是O(nm + cm²)。。

　　實際編碼過程中，DATrie代碼難度大過多路查找樹，主要是狀態的表示不如樹結構那樣的清晰，下標很容易搞混掉。
　　有個地方需要注意的是，base值正數表示起始偏移量，負數表示該狀態為終止態，所以在查找新base值時，要保證查到的值是正數。
如：空Trie狀態下，插入d時，因為第一個空地址是1，所以得到base=1-4=-3，這樣base正負的含義就被破壞了。

　　4.1.4 Trie樹的應用

　　Trie是一種非常簡單高效的數據結構，但有大量的應用實例。

　　（1）字符串檢索

　　事先將已知的一些字符串（字典）的有關信息保存到trie樹里，查找另外一些未知字符串是否出現過或者出現頻率。例如：

　　1）給出N個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現的順序寫出所有不在熟詞表中的生詞。

　　2）給出一個詞典，其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本，文本的每一行也由小寫字母構成。判斷文本中是否含有任何不良單詞。例如，若rob是不良單詞，那么文本problem含有不良單詞。

　　（2）字符串最長公共前綴

　　Trie樹利用多個字符串的公共前綴來節省存儲空間，反之，當我們把大量字符串存儲到一棵trie樹上時，我們可以快速得到某些字符串的公共前綴。

　　例如：給出N個小寫英文字母串，以及Q個詢問，即詢問某兩個串的最長公共前綴的長度是多少？

　　解決方案：首先對所有的串建立其對應的字母樹。此時發現，對于兩個串的最長公共前綴的長度即它們所在結點的公共祖先個數，于是，問題就轉化為了離線（Offline）的最近公共祖先（LeastCommon Ancestor，簡稱LCA）問題。

　　而最近公共祖先問題同樣是一個經典問題，可以用下面幾種方法：

　　1）利用并查集（Disjoint Set），可以采用采用經典的Tarjan算法；

　　2）求出字母樹的歐拉序列（Euler Sequence）后，就可以轉為經典的最小值查詢（Range Minimum Query，簡稱RMQ）問題

　　（3）排序

　　Trie樹是一棵多叉樹，只要先序遍歷整棵樹，輸出相應的字符串便是按字典序排序的結果。例如：給你N個互不相同的僅由一個單詞構成的英文名，讓你將它們按字典序從小到大排序輸出。

　　（4）作為其他數據結構和算法的輔助結構，如后綴樹，AC自動機等

　　4.1.5 Trie樹復雜度分析

　　（1）插入、查找的時間復雜度均為O(N)，其中N為字符串長度。

　　（2）空間復雜度是26^n級別的，非常龐大（可采用雙數組實現改善）。

　　4.1.6 總結

　　Trie樹是一種非常重要的數據結構，它在信息檢索，字符串匹配等領域有廣泛的應用，同時，它也是很多算法和復雜數據結構的基礎，如后綴樹，AC自動機等。

　　4.2 TrieMemory

　　Trie Memory^[9]是一種在內存中存儲和檢索信息的方式，這種方式的優點是訪問速度快，具有冗余存儲信息的優點，主要的缺點是存儲空間利用率很低。

　　4.2.1 基本的Trie Memory模型

　　假設我們需要跟蹤一系列的單詞集合，這些集合是字母組成的序列。這些單詞序列有各種各樣的長度，我們必須記住的是這些字母組成的有限序列在這個集合中。總得來說，我們需要判斷一個序列是不是這個集合的成員。
　　剛開始trie僅僅是register組成的一個集合，除此之外還有兩個register，一個是α另一個是δ，每一個register都有cell來存儲整個字母表，如果我們要存儲“space”的話，每個register必須擁有27個cell。
每一個cell都有空間來存儲其它register在內存中的地址，trie中的cell還沒有用來存儲信息，通常包含的是register α的地址信息。一個cell如果包含了非register α的register地址，則它表示存儲了信息，這些信息代表了這個cell的名稱，“A”表示A cell,“B”表示B cell。下一個register的地址在序列中。
　　下面用一個例子(圖2.1)來說明，為了讓例子簡單些，我們使用字母表的前5個字符來表示整體。然后用▽表示“space”，假設我們想存儲DAB,BAD,BADE,BE,BED,BEAD,CAB,CAD和A，接下來用圖來說明整個流程。在圖中每一行代表一個register，每個register有6個cell,最后一行代表第三個特殊的register叫做portal register,是我們進入系統內存的通道它除了是入口外，也和其它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”放入▽單元，它是終止參數，至此DAB存儲結束。然后我們轉到第二個單詞BAD，引入地址“5”進入portal register的B單元格來表示字母B，然后到register 5的A單元格寫入地址“6”，再到register 6的D單元格寫入地址“7”，最后到register 7的▽單元格寫入地址“1”。當我們開始存儲BADE時，我們發現B,A,D已經在trie中了，因此我們沿著已經存在的BAD的路徑到register 7然后引入地址“8”到單元格E中去，然后把地址“1”放入register 8的▽單元。

　　4.2.2 Register的類型

　　在剛才提到的結構中我們可以把register分為4種類型：

　　1）α(address) register來指向下一個存儲信息的地址

　　2）δ(deletion) register

　　3）ν(next) register，下一步將要存儲的信息(在空內存中，它是portal register)

　　4）χ(exterior)類型χ是所有register中還沒有接受存儲信息并且沒有被指向為下一個存儲位置的register。

　　5）ο(occupied)類型ο是存有信息的register

　　4.2.3 Trie的讀和寫

　　在上述的所有的register中除了χ都在trie中，存儲和讀取操作現在能夠被簡單的公平的定義如下。

　　4.2.3.1 寫操作

　　1）把第i個參數字符傳入下一個register，如果是第一個字符，則是portal register

　　2）選擇對應字符串的的cell,如果第i個參數字符是字母表的第j個字符，選擇第j個cell。

　　3）檢測來自第i個單元的聯結

　　4）如果這種聯結使得register α：

　　a） 通過αregister把聯結投射到鏈接的頭部，這樣就可以存儲信息。

　　b)投射從αregister到鏈接頭部的聯結來創建一個“next”register(ν)

　　c)最后，把所有的從ν發出來的聯結指向αregister。

　　5）如果源于第j個cell的聯結指向非 αregister的話，移動到那個register去：

　　a） 如果是第一個register，這參數是一個存儲集合的成員(結束流程)。

　　b）如果不是register 1的話，i加1并且轉到第二步去。

　　4.2.3.2 讀操作

　　使用相同的流程，但是不要使用投射，不要投射任何關系，如果聯結指向register 1，則這個參數是存儲集合的一個成員，如果任何點的聯結指向αregister,換句話說這個參數不是存儲集合的成員。

　　5 HASH索引

　　HASH就是把關鍵詞直接映射為存儲地址，達到快速尋址的目的，即Addr=H(key)，其中key為關鍵詞；H為哈希函數。主要有以下幾種常用的哈希函數：

　　1)除留余數法(DivisionMethod)，H(key)=keyMOD p，p一般為質數；

　　2)隨機數法(RandomMethod)，H(key)=random(key)，random為隨機函數；

　　3)平方取中法(MidsquareMethod)。

　　HASH索引結構不需要額外的存儲空間，并且能夠在O(1)的時間復雜度下準確定位到所查找的數據，將磁盤數據庫中的數據查找時間代價優化至最小。Hash索引結構由于以上優點在磁盤數據庫中廣泛的運用。經歷長久的研究，先后發展出了鏈接桶哈希(chainedbucket hash)^[10]，可擴展哈希(extendible hash)^[11]、線性哈希(linearhash)^[12]和修正的線性哈希(modified linear hash)^[13]。但是這些哈希算法雖然針對內存數據庫進行了少許優化，但是與傳統數據庫中所用的哈希算法沒有明顯不同。到了2007年，KennethA. Ross提出了基于現代處理器的Hash預取算法^[14]將SIMD指令集融入到Hash算法中，才真正從內存索引的角度改進了哈希算法，提升數據組織的效率。

　　5.1 鏈接桶哈希

　　鏈接桶哈希（圖5-1）是一個靜態的結構，可用于內存中與磁盤中。因為它是靜態結構，不用對數據進行重組織，所以它速度很快。但這也是它的缺陷，面對動態數據，就顯得不合適了，因為鏈接桶哈希必須在使用之前知道哈希表的大小，而這恰恰很難預測。如果預測的表大小過小，其性能會大受影響；如果過大，空間浪費較為嚴重。最好情況下，它只有一些空間的浪費，用來存放指向下一個桶的指針。

　　5.2 可擴展哈希

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

　　5.3 線性哈希

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

　　5.4 修正的線性哈希

　　修正的線性哈希相對于線性哈希主要面向內存環境。通過使用更大的連續節點替代目錄，普通的線性哈希由于有空節點而浪費空間。而且，除非有一個巧妙的方案解決潛在的虛擬內存映射機制問題，不然每次目錄增長時那個連續的節點都要被拷貝到一個更大的內存塊。修正的線性哈希采用跟可擴展哈希一樣的目錄，除了目錄為線性增長的，鏈接的是單個項目的節點和分配內存是從一個常規的內存池。這個算法節點分裂的準則是基于性能，舉例來說，監控哈希鏈的平均長度比監控存儲利用率能夠更直接的控制平均搜索和更新時間^[13]。

　　5.5 Hash預取算法

　　Hash預取算法面向的是鍵和哈希值都是32位的場景，特地對內存環境進行了優化。此算法使用乘法散列，這種方法十分普遍、計算高效，更重要的是適用于矢量，達到了一次計算多個哈希函數的目的^[14]。針對現代處理器的SIMD架構，將鍵值與哈希值共同放在一個指令當中，達到大大減少指令數的目的，令每次所需的數據長度恰好等于L2的cacheline，大大降低了性能代價，在內存環境中，大大提高了cache的性能。

　　參考文獻：

　　[1] Garcia-Molina H, Salem K. Main memorydatabase systems: An overview[J]. Knowledge and Data Engineering, IEEETransactions on, 1992, 4(6): 509-516.

　　[2] Moore G E. Cramming more components ontointegrated circuits[J]. 1965.

　　[3] Lehman T J, Carey M J. A study of indexstructures for main memory database management systems[C]//Conference on VeryLarge Data Bases. 1986, 294.

　　[4] Jun Rao,Kenneth A. Ross:CacheConscious Indexing for Decision-Support in Main Memory,VLDB 1999: 78-89

　　[5]RaghuRamakrishnan. Database Management Systems. McGraw-Hill, 1997.

　　[6] AndrewYao. On random 2-3 trees. Acta Informatica, 9:159{170, 1978.

　　[7]Black,Paul E. (2009-11-16). "trie". Dictionary of Algorithms and Data Structures. NationalInstitute of Standards and Technology. Archived from the original on2010-05-19.

　　[8] Knuth,Donald(1997). "6.3: Digital Searching".The Art of ComputerProgramming Volume 3: Sorting and Searching.Addison-Wesley.p.492.

　　[9] FREDKIN E.Tire Memory[J]. Communication of theACM,1960,3(9):490-499.

　　[10] Knuth D. The Art of ComputerProgramming 1: Fundamental Algorithms 2: Seminumerical Algorithms 3: Sortingand Searching[J]. 1968.

　　[11] Fagin R, Nievergelt J, Pippenger N, et al.Extendible hashing—a fast access method for dynamic files[J]. ACM Transactionson Database Systems (TODS), 1979, 4(3): 315-344.

　　[12] Litwin W. Linear Hashing: a new tool forfile and table addressing[C]//VLDB. 1980, 80: 1-3.

　　[13] Lehman T J, Carey M J. A study of indexstructures for main memory database management systems[C]//Conference on VeryLarge Data Bases. 1986, 294.

　　[14] Ross K A. Efficient Hash Probes on ModernProcessors[C]//ICDE. 2007: 1297-1301.