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

時(shí)間：2022-05-25 01:03:01 | 來源：網(wǎng)絡(luò)營銷

時(shí)間：2022-05-25 01:03:01 來源：網(wǎng)絡(luò)營銷

傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)把所有數(shù)據(jù)都放在磁盤上進(jìn)行管理，所以稱作磁盤數(shù)據(jù)庫（DRDB:Disk-Resident Database），磁盤數(shù)據(jù)庫需要頻繁地訪問磁盤來進(jìn)行數(shù)據(jù)的操作，磁盤的讀寫速度遠(yuǎn)遠(yuǎn)小于CPU處理數(shù)據(jù)的速度，所以磁盤數(shù)據(jù)庫的瓶頸出現(xiàn)在磁盤讀寫上。

基于此，內(nèi)存數(shù)據(jù)庫的概念被提出來了，內(nèi)存數(shù)據(jù)庫(MMDB:Main Memory Database，也叫主存數(shù)據(jù)庫)就是將數(shù)據(jù)全部或者大部分放在內(nèi)存中進(jìn)行操作的數(shù)據(jù)庫管理系統(tǒng)，對(duì)查詢處理、并發(fā)控制與恢復(fù)的算法和數(shù)據(jù)結(jié)構(gòu)進(jìn)行重新設(shè)計(jì)，以更有效地使用CPU周期和內(nèi)存。

相對(duì)于磁盤，內(nèi)存的數(shù)據(jù)讀寫速度要高出幾個(gè)數(shù)量級(jí)，將數(shù)據(jù)保存在內(nèi)存中相比從磁盤上訪問能夠極大地提高應(yīng)用的性能。

近十幾年來，內(nèi)存的發(fā)展一直遵循摩爾定律，內(nèi)存的價(jià)格一直下降，而內(nèi)存的容量一直在增加，現(xiàn)在的主流服務(wù)器，幾百GB或者幾TB的內(nèi)存都很常見，內(nèi)存的發(fā)展使得內(nèi)存數(shù)據(jù)庫得以實(shí)現(xiàn)。

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

一、T-tree

T-tree是針對(duì)主存訪問優(yōu)化的索引技術(shù)，T-tree是一種一個(gè)節(jié)點(diǎn)中包含多個(gè)索引條目的平衡二叉樹，T-tree的索引項(xiàng)無論是從大小還是算法上都比B-tree精簡得多。

1、T-tree的結(jié)構(gòu)及特點(diǎn)


T-Tree的結(jié)點(diǎn)

T-tree的搜索算法不分搜索的值在當(dāng)前的節(jié)點(diǎn)還是在內(nèi)存中的其他地方，每訪問到一個(gè)新的索引節(jié)點(diǎn)，索引的范圍減少一半。

T-tree索引用來實(shí)現(xiàn)關(guān)鍵字的范圍查詢，T-tree是一棵特殊平衡的二叉樹（AVL），它的每個(gè)節(jié)點(diǎn)存儲(chǔ)了按鍵值排序的一組關(guān)鍵字，T-tree除了較高的節(jié)點(diǎn)空間占有率，遍歷一棵樹的查找算法在復(fù)雜程度和執(zhí)行時(shí)間上也占有優(yōu)勢(shì)，現(xiàn)在T-tree己經(jīng)成為內(nèi)存數(shù)據(jù)庫中最主要的一種索引方式。

T-tree具有以下特點(diǎn)：

（1）、左子樹與右子樹之差不超過1。

（2）、在一個(gè)存儲(chǔ)節(jié)點(diǎn)可以保存多個(gè)鍵值，它的最左與最右鍵值分別為這個(gè)節(jié)點(diǎn)的最小與最大鍵值，它的左子樹僅僅包含那些鍵值小于或等于最小鍵值的一記錄，同理右子樹只包括那些鍵值大于或等于最大鍵值的記錄。

（3）、同時(shí)擁有左右子樹的節(jié)點(diǎn)被稱為內(nèi)部節(jié)點(diǎn)，只擁有一個(gè)子樹的節(jié)點(diǎn)被稱為半葉節(jié)點(diǎn)，沒有子樹的節(jié)點(diǎn)被稱為葉子。

（4）、為了保持空間的利用率，每一個(gè)內(nèi)部節(jié)點(diǎn)都需要包含一個(gè)最小數(shù)目的鍵值。

由此可知，T-tree是一個(gè)每個(gè)結(jié)點(diǎn)含有多個(gè)關(guān)鍵字的平衡二叉樹，每個(gè)節(jié)點(diǎn)內(nèi)的關(guān)鍵字有序排列，左子樹都要比根節(jié)點(diǎn)關(guān)鍵字小，右子樹都要比根節(jié)點(diǎn)關(guān)鍵字大。

在上述T-tree結(jié)點(diǎn)結(jié)構(gòu)中，億企邦覺得還包含如下信息：

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

（2）、Left_child_ptr和Right_child_ptr分別表示當(dāng)前結(jié)點(diǎn)的左子樹和右子樹指針；

（3）、Max_Item表示結(jié)點(diǎn)中所能容納的鍵值的最大數(shù)；

（4）、Key[0]至K[Max_Item-1]為結(jié)點(diǎn)內(nèi)存放的關(guān)鍵字；

（5）、nItem是當(dāng)前節(jié)點(diǎn)實(shí)際存儲(chǔ)的關(guān)鍵字個(gè)數(shù)。

對(duì)于T-tree有如下特征：

（1）、與AVL樹相似，T-tree中任何結(jié)點(diǎn)的左右子樹的高度之差最大為1；

（2）、與AVL樹不同，T-tree的結(jié)點(diǎn)中可存儲(chǔ)多個(gè)鍵值，并且這些鍵值排列有序；

（3）、T-tree結(jié)點(diǎn)的左子樹中容納的鍵值不大于該結(jié)點(diǎn)中的最左鍵值；右子樹中容納的鍵值不小于該結(jié)點(diǎn)中的最右鍵值；

（4）、為了保證每個(gè)結(jié)點(diǎn)具有較高的空間占用率，每個(gè)內(nèi)部結(jié)點(diǎn)所包含的鍵值數(shù)目必須不小于某個(gè)指定的值，通常為(Max_Item-2)(Max_Item為結(jié)點(diǎn)中最大鍵值目)。

2、T-tree索引的操作

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

（1）、查找

T-tree的查找類似于二叉樹，不同之處主要在于每一結(jié)點(diǎn)上的比較不是針對(duì)結(jié)點(diǎn)中的各個(gè)元素值，而是首先檢查所要查找的目標(biāo)鍵值是否包含在當(dāng)前結(jié)點(diǎn)的最左鍵值和最右鍵值所確定的范圍內(nèi)，如果是的話，則在當(dāng)前結(jié)點(diǎn)的鍵值列表中使用二分法進(jìn)行查找。

如果目標(biāo)鍵值小于當(dāng)前結(jié)點(diǎn)的最左鍵值，則類似地搜索當(dāng)前結(jié)點(diǎn)的左孩子結(jié)點(diǎn)；如果目標(biāo)鍵值大于當(dāng)前結(jié)點(diǎn)的最右鍵值，則類似地搜索當(dāng)前結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。

（2）、插入

T-tree的插入是以查找為基礎(chǔ)，應(yīng)用查找操作定位目標(biāo)鍵值插入位置，并記下查找過程所遇到的最后結(jié)點(diǎn)。

如果查找成功，判斷此結(jié)點(diǎn)中是否有足夠的存儲(chǔ)空間，如果有，則將目標(biāo)鍵值插入結(jié)點(diǎn)中；否則將目標(biāo)鍵值插入此結(jié)點(diǎn)，然后將結(jié)點(diǎn)中的最左鍵值插入到它的左子樹中(此時(shí)是遞歸插入操作)，之后結(jié)束。

否則分配新結(jié)點(diǎn)，并插入目標(biāo)鍵值，然后根據(jù)目標(biāo)鍵值與結(jié)點(diǎn)的最大最小鍵值之間的關(guān)系，將新分配的結(jié)點(diǎn)鏈接為結(jié)點(diǎn)的左孩子或右孩子，對(duì)樹進(jìn)行檢查，判斷T-tree的平衡因子是否滿足條件，如果平衡因子不滿足則執(zhí)行旋轉(zhuǎn)操作。

（3）、刪除

T-tree的刪除操作也是以查找為基礎(chǔ)，應(yīng)用查找操作定位目標(biāo)鍵值。

如果查找失敗，則結(jié)束；否則令N為目標(biāo)鍵值所在的結(jié)點(diǎn)，并從結(jié)點(diǎn)N中刪除目標(biāo)鍵值；刪除節(jié)點(diǎn)后，如果結(jié)點(diǎn)N為空，則刪除結(jié)點(diǎn)N，并對(duì)樹的平衡因子進(jìn)行檢查，判斷是否需要執(zhí)行旋轉(zhuǎn)操作；如果結(jié)點(diǎn)N中的鍵值數(shù)量少于最小值，則根據(jù)N的平衡因子決定從結(jié)點(diǎn)N的左子樹中移出最大的鍵值或者右子樹中移出最小值來填充。

3、T-tree索引實(shí)現(xiàn)關(guān)鍵技術(shù)

實(shí)現(xiàn)T-tree索引即要實(shí)現(xiàn)T-tree的查找，插入和刪除，其中又以查找為基礎(chǔ)，對(duì)T-tree的維護(hù)也就是T-tree的旋轉(zhuǎn)為關(guān)鍵，當(dāng)由于插入或刪除鍵值導(dǎo)致樹的失衡，則要進(jìn)行T-tree的旋轉(zhuǎn)，使之重新達(dá)到平衡。

在插入情況下，需要依次對(duì)所有沿著從新創(chuàng)建結(jié)點(diǎn)到根結(jié)點(diǎn)路徑中的結(jié)點(diǎn)進(jìn)行檢查，直到出現(xiàn)如下兩種情況之一時(shí)中止：某個(gè)被檢查結(jié)點(diǎn)的兩個(gè)子樹高度相等，此時(shí)不需要執(zhí)行旋轉(zhuǎn)操作；某個(gè)被檢查結(jié)點(diǎn)的兩個(gè)子樹的高度之差大于1，此時(shí)對(duì)該結(jié)點(diǎn)僅需執(zhí)行一次旋轉(zhuǎn)操作即可。

在刪除情況下，類似地需要依次對(duì)所有沿著從待刪除結(jié)點(diǎn)的父結(jié)點(diǎn)到根結(jié)點(diǎn)路徑中的結(jié)點(diǎn)進(jìn)行檢查，在檢查過程中當(dāng)發(fā)現(xiàn)某個(gè)結(jié)點(diǎn)的左右子樹高度之差越界時(shí)，需要執(zhí)行一次旋轉(zhuǎn)操作，與插入操作不同的是，執(zhí)行完旋轉(zhuǎn)操作之后，檢查過程不能中止，而是必須一直執(zhí)行到檢查完根結(jié)點(diǎn)。

由此可以看出，對(duì)于插入操作，最多只需要一次旋轉(zhuǎn)操作即可使T-tree恢復(fù)到平衡狀態(tài)；而對(duì)于刪除操作則可能會(huì)引起向上的連鎖反應(yīng)，使高層結(jié)點(diǎn)發(fā)生旋轉(zhuǎn)，因而可能需要進(jìn)行多次旋轉(zhuǎn)操作。

為了對(duì)T-tree進(jìn)行平衡，需要進(jìn)行旋轉(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)。插入時(shí)的情況與刪除類似。

二、CSS/CSB+樹

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

1、FULL CSS-Tree

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

CSS-Tree的結(jié)點(diǎn)可以存儲(chǔ)在數(shù)組中，如圖3-2所示：

（1）、構(gòu)造FULL CSS-Tree

將一個(gè)已排好序的數(shù)組構(gòu)造一棵相應(yīng)的Full CSS-Tree，首先將數(shù)組分為兩部分，并且在葉子節(jié)點(diǎn)和數(shù)組元素間建立匹配，然后從最后一個(gè)內(nèi)部節(jié)點(diǎn)開始，將節(jié)點(diǎn)直接左子樹的最大鍵值作為節(jié)點(diǎn)入口。

對(duì)于某一些內(nèi)部節(jié)點(diǎn)，也就是最深層最后一個(gè)葉子節(jié)點(diǎn)的祖先，可能完全鍵值，可以用數(shù)組前半部分最后的一個(gè)元素來填充這些鍵值，所以在某些內(nèi)部節(jié)點(diǎn)會(huì)有一些復(fù)制的鍵值，盡管要增量更新一棵Full CSS-Tree樹是很困難的，但構(gòu)造這樣一棵樹花費(fèi)并不大。

實(shí)驗(yàn)表明對(duì)于有著兩千五百萬鍵值的數(shù)組，構(gòu)造其相應(yīng)的Full CSS-Tree花費(fèi)的時(shí)間不足一秒。

（2）、查詢Full CSS-Tree

從根節(jié)點(diǎn)開始，每次都查詢一個(gè)內(nèi)部節(jié)點(diǎn)，利用二分查找來決定查找哪一個(gè)分支，重復(fù)上述行為直到葉子節(jié)點(diǎn)，最后將葉子節(jié)點(diǎn)與排好序的數(shù)組進(jìn)行匹配。

在節(jié)點(diǎn)內(nèi)所有的查詢都由if-else構(gòu)成，在內(nèi)部節(jié)點(diǎn)進(jìn)行二分查找時(shí)，一直比較左邊的鍵值是否不小于要查詢的鍵值，當(dāng)找到第一個(gè)比要查詢的鍵值小時(shí)，停止比較并進(jìn)入右邊的分支（如果找不到這樣的值，就進(jìn)入最左邊的分支）。

這樣可以保證當(dāng)在節(jié)點(diǎn)中有復(fù)制的值時(shí)，我們可以在所有復(fù)制的鍵值中找到最左邊的鍵值。

2、LevelCSS-Tree

對(duì)于每個(gè)節(jié)點(diǎn)有m個(gè)記錄的Full CSS-Tree，有嚴(yán)格的m個(gè)鍵值，所有的記錄都會(huì)被利用到，對(duì)于m=2t，我們定義每個(gè)節(jié)點(diǎn)只有只有m-1條記錄，并且有一個(gè)分支因子m。

一棵Level CSS-Tree樹比一棵相應(yīng)的Full CSS-Tree樹的深度大，因?yàn)榉种б蜃邮莔而不是m+1，然后對(duì)于每一個(gè)節(jié)點(diǎn)，需要的同伴數(shù)更少。

若N為一個(gè)已排好序的數(shù)組元素所對(duì)應(yīng)的節(jié)點(diǎn)數(shù)，Level CSS-Tree有l(wèi)ogmN層，而Full CSS-Tree有l(wèi)ogm+1N層，每個(gè)節(jié)點(diǎn)的同伴數(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個(gè)cache accesses，遍歷logmN個(gè)節(jié)點(diǎn)，而Full CSS-Tree需logm+1N。

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

3、CSB+-Tree

盡管CSS-Tree相比二分查找和T-Trees查詢性能更好，但是它是用于決策支持的有著相對(duì)靜態(tài)數(shù)據(jù)的工作負(fù)載設(shè)計(jì)的。

CSB+-Tree(CacheSensitive B+-Trees)是B+-Trees的變體，連續(xù)存儲(chǔ)給定節(jié)點(diǎn)的子節(jié)點(diǎn)，并且只存儲(chǔ)節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)的地址，其他子節(jié)點(diǎn)的地址可以通過相對(duì)這個(gè)子節(jié)點(diǎn)的偏移量計(jì)算獲得，由于只存儲(chǔ)一個(gè)子節(jié)點(diǎn)的指針，cache的利用率是很高的，與B+-Tree類似，CSB+-Tree支持增量更新。

CSB+-Tree有兩種變體，分段CSB+-Tree(SegmentedCSB+-tree)和完全CSB+-tree(FullCSB+-Tree)分段CSB+-Tree將子節(jié)點(diǎn)分段，在同一段的子節(jié)點(diǎn)連續(xù)存儲(chǔ)，在每個(gè)節(jié)點(diǎn)中，只有每一段的起始地址才會(huì)被存儲(chǔ)。

當(dāng)有分裂時(shí)，分段CSB+-Tree可以減少復(fù)制開銷，因?yàn)橹挥幸粋€(gè)分段需要移動(dòng)，完全CSB+-Tree為整個(gè)節(jié)點(diǎn)重新分配空間，因此減少了分裂開銷。

（1）、CSB+-Tree上的操作

①、Bulkload.

對(duì)于CSB+-Tree樹，一個(gè)有效的bulkload方法就是一層一層的建立索引結(jié)構(gòu)，為每一個(gè)葉節(jié)點(diǎn)分配空間，計(jì)算在高層需要的節(jié)點(diǎn)數(shù)，并給該層分配連續(xù)的存儲(chǔ)空間，通過將低層每一個(gè)節(jié)點(diǎn)的最大值填入高層的節(jié)點(diǎn)，并設(shè)置每一個(gè)高層節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)指針，重復(fù)上述操作直到高層只有一個(gè)節(jié)點(diǎn)，且這個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，因?yàn)橥粚拥乃泄?jié)點(diǎn)是連續(xù)的，所以構(gòu)造節(jié)點(diǎn)組無需額外的復(fù)制操作。

②、Search

查詢CSB+-Tree與查詢B+-Tree類似，當(dāng)最右邊節(jié)點(diǎn)的鍵值K比要查詢的鍵值小，給第一個(gè)子節(jié)點(diǎn)增加K的偏移量來獲得子節(jié)點(diǎn)的地址。

例如，K是節(jié)點(diǎn)的第三個(gè)鍵值，可以用一個(gè)c語句找到子節(jié)點(diǎn)：child=first_child+3，其中child和first_child是節(jié)點(diǎn)的指針。

③、Insertion

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

當(dāng)需要分裂葉節(jié)點(diǎn)時(shí)，基于父節(jié)點(diǎn)是否有足夠的空間存放鍵值會(huì)產(chǎn)生兩種情況，假設(shè)父節(jié)點(diǎn)p有足夠的空間，令f為p的第一個(gè)子節(jié)點(diǎn)的指針，g為f指向的節(jié)點(diǎn)組，構(gòu)建一個(gè)新的比g多了一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)組g’，將g中所有的節(jié)點(diǎn)復(fù)制到g’，g中要分裂的節(jié)點(diǎn)在g’中變?yōu)閮蓚€(gè)節(jié)點(diǎn)，更新p中第一個(gè)子節(jié)點(diǎn)的指針f，使它指向g’，并且重新分配g。

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

④、Deletion

刪除操作類似于插入操作，一般的，簡單的定位數(shù)據(jù)入口并且加以刪除。無需調(diào)整樹保證50%的occupancy。

（2）、Segmented CSB+-Tree

考慮128字節(jié)的cache-line，CSB+-Tree中每個(gè)節(jié)點(diǎn)最多有30個(gè)鍵值，意味著每個(gè)節(jié)點(diǎn)可以有31個(gè)子節(jié)點(diǎn)，那么一個(gè)節(jié)點(diǎn)組最大可達(dá)31*128近4KB，因此每一個(gè)分裂，需要復(fù)制4KB的數(shù)據(jù)來創(chuàng)建一個(gè)節(jié)點(diǎn)組，若cache-line更大，分裂一個(gè)節(jié)點(diǎn)的開銷將會(huì)更大。

修改節(jié)點(diǎn)結(jié)構(gòu)可以減少分裂時(shí)的復(fù)制操作?？梢詫⒆庸?jié)點(diǎn)分段，將每一段的地址存儲(chǔ)在節(jié)點(diǎn)中，每一段形成了一個(gè)節(jié)點(diǎn)組，只有在同一段的子節(jié)點(diǎn)被連續(xù)存儲(chǔ)。

第一種考慮是固定每一個(gè)分段的大小，填充第一個(gè)分段的節(jié)點(diǎn)，一旦第一個(gè)分段滿了，就將節(jié)點(diǎn)放在第二個(gè)分段，若一個(gè)節(jié)點(diǎn)落在第二個(gè)分段，我們只需將第二個(gè)分段的節(jié)點(diǎn)復(fù)制到新的段中，而無需管第一個(gè)分段，若新的節(jié)點(diǎn)落在第一個(gè)分段(已經(jīng)滿了)，我們需要將數(shù)據(jù)從第一個(gè)分段移至第二個(gè)分段，在上述例子中，針對(duì)隨機(jī)插入，分裂產(chǎn)生的數(shù)據(jù)復(fù)制將會(huì)減少至1/2(1/2+3/4)*4KB=2.5KB。

另一種就是允許每個(gè)分段的大小不同，最終將節(jié)點(diǎn)分為兩段，當(dāng)有節(jié)點(diǎn)插入時(shí)，為這個(gè)節(jié)點(diǎn)所屬的分段創(chuàng)建一個(gè)新的分段，并更新相應(yīng)分段的大小，在這種方法中，嚴(yán)格來說每次插入只涉及到一個(gè)分段(但當(dāng)父節(jié)點(diǎn)也需要分裂，此時(shí)兩個(gè)分段都要復(fù)制)，若一個(gè)新的節(jié)點(diǎn)等可能的落入其中一個(gè)分段，一個(gè)分裂產(chǎn)生的數(shù)據(jù)復(fù)制量為1/2*4KB=2KB，這種方法可以進(jìn)一步的減少數(shù)據(jù)復(fù)制量。

有兩個(gè)分段的SegmentedCSB+Tree如圖3-3所示(每個(gè)葉節(jié)點(diǎn)只有兩個(gè)鍵值)：

分段CSB+-Tree可支持所有對(duì)樹的操作，方法與非分段CSB+-Tree類似，然而，查找每個(gè)節(jié)點(diǎn)的右孩子比起非分段的CSB+-Tree的開銷大，因?yàn)樾枰业胶⒆铀诘姆侄巍?br>
（3）、FULLCSB+-Tree

在FULLCSB+-Tree中，節(jié)點(diǎn)分裂的開銷比CSB+-Tree小，在CSB+-Tree中，當(dāng)節(jié)點(diǎn)分裂時(shí)，需要將節(jié)點(diǎn)組整個(gè)復(fù)制到新的組中，而在FullCSB+-Tree中，只需訪問節(jié)點(diǎn)組的一半。

對(duì)于這種轉(zhuǎn)移操作的源地址和目的地址有大的交叉，訪問的cache-line的數(shù)目限制在s內(nèi)，F(xiàn)ULLCSB+-Tree在分裂上的平均時(shí)間開銷是0.5s，而CSB+-Tree需時(shí)2s。

4、時(shí)間空間分析

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


圖 3-5 CSB+-Tree查詢時(shí)間分析

圖3-5顯示了各種方法間分支因子、鍵值差異數(shù)、cache未命中數(shù)、每個(gè)節(jié)點(diǎn)其他差異的比較，B+-Tree的分支因子比CSS-Tree小，而CSB+-Tree存儲(chǔ)的子節(jié)點(diǎn)指針少，所需的分支因子與CSS-Tree相近，這導(dǎo)致每個(gè)方法的cache未命中次數(shù)不一樣，節(jié)點(diǎn)的分支因子越大，cache未命中次數(shù)相應(yīng)的越小。

在CSB+-Tree每增加一個(gè)分段，分支因子就會(huì)減少2，這是由于需要一個(gè)槽來存儲(chǔ)子節(jié)點(diǎn)指針，另一個(gè)槽來存儲(chǔ)新增分段的大小。

一般而言，B+-Tree中節(jié)點(diǎn)的70%空間是滿的，需要相應(yīng)的調(diào)整分支因子大小。

圖3-6顯示了在分裂時(shí)預(yù)期要訪問的cache-line數(shù)，由于復(fù)制時(shí)源地址和目的地址有交叉，所以FullCSB+-Tree所需的數(shù)目小，分裂開銷是插入操作總開銷的一部分，另一部分是定位優(yōu)葉子節(jié)點(diǎn)產(chǎn)生的查詢開銷。分裂開銷相對(duì)獨(dú)立于樹的深度，這是由于大多數(shù)的分裂都發(fā)生在葉節(jié)點(diǎn)。

然而，當(dāng)樹的規(guī)模越來越大時(shí)，相應(yīng)的查詢產(chǎn)生的開銷也會(huì)增大，CSB+-Tree的分裂開銷比B+-Tree大，但是插入產(chǎn)生的總開銷還與樹的規(guī)模有關(guān)。

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

三、Trie-tree索引

Trie-Tree又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種，典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)，它的優(yōu)點(diǎn)是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。


圖展示了一個(gè)基本的tire-tree結(jié)構(gòu)

1、Trie-tree性質(zhì)

一般來說，Trie-tree有三個(gè)基本的性質(zhì)：

（1）、根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)以外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。

（2）、從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的的字符連接起來，為改節(jié)點(diǎn)對(duì)應(yīng)的字符串。

（3）、每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

2、Trie樹的基本實(shí)現(xiàn)

字母樹的插入、刪除和查找都非常簡單，用一個(gè)一重循環(huán)即可，即第i次循環(huán)找到前i個(gè)字母所對(duì)應(yīng)的子樹，然后進(jìn)行相應(yīng)的操作，實(shí)現(xiàn)這棵字母樹，我們用最常見的數(shù)組保存（靜態(tài)開辟內(nèi)存）即可，當(dāng)然也可以開動(dòng)態(tài)的指針類型（動(dòng)態(tài)開辟內(nèi)存）。

至于結(jié)點(diǎn)對(duì)兒子的指向，一般有三種方法：

（1）、對(duì)每個(gè)結(jié)點(diǎn)開一個(gè)字母集大小的數(shù)組，對(duì)應(yīng)的下標(biāo)是兒子所表示的字母，內(nèi)容則是這個(gè)兒子對(duì)應(yīng)在大數(shù)組上的位置，即標(biāo)號(hào)。

（2）、對(duì)每個(gè)結(jié)點(diǎn)掛一個(gè)鏈表，按一定順序記錄每個(gè)兒子是誰。

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

在億企邦看來，這三種方法，各有特點(diǎn)，第一種易實(shí)現(xiàn)，但實(shí)際的空間要求較大；第二種，較易實(shí)現(xiàn)，空間要求相對(duì)較小，但比較費(fèi)時(shí)；第三種，空間要求最小，但相對(duì)費(fèi)時(shí)且不易寫。

3、實(shí)現(xiàn)方法

搜索字典項(xiàng)目的方法為：

（1）、從根結(jié)點(diǎn)開始一次搜索。

（2）、取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對(duì)應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索。

（3）、在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個(gè)字母,并進(jìn)一步選擇對(duì)應(yīng)的子樹進(jìn)行檢索。

（4）、迭代過程……。

（5）、在某個(gè)結(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找。

其他操作類似處理

（1）、Trie原理

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

（2）、Trie樹的高級(jí)實(shí)現(xiàn)Double-Array實(shí)現(xiàn)

可以采用雙數(shù)組（Double-Array）實(shí)現(xiàn)，如圖1.3，利用雙數(shù)組可以大大減小內(nèi)存使用量，具體實(shí)現(xiàn)方法是：

兩個(gè)數(shù)組，一個(gè)是base[]，另一個(gè)是check[]，設(shè)數(shù)組下標(biāo)為i，如果base[i], check[i]均為0，表示該位置為空，如果base[i]為負(fù)值，表示該狀態(tài)為終止態(tài)（即詞語），check[i]表示該狀態(tài)的前一狀態(tài)。

定義1、對(duì)于輸入字符c，從狀態(tài)s轉(zhuǎn)移到狀態(tài)t，雙數(shù)組字典樹滿足如下條件：

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

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

我們知道雙數(shù)組的實(shí)現(xiàn)方法是當(dāng)狀態(tài)有新轉(zhuǎn)移時(shí)才分配空間給新狀態(tài)，或可以表述為只分配需要轉(zhuǎn)移的狀態(tài)的空間，當(dāng)遇到無法滿足上述條件時(shí)再進(jìn)行調(diào)整，使得其base值滿足上述條件，這種調(diào)整只影響當(dāng)前節(jié)點(diǎn)下一層節(jié)點(diǎn)的重分配，因?yàn)樗泄?jié)點(diǎn)的地址分配是靠base數(shù)組指定的起始下標(biāo)所決定的。

插入的操作，假設(shè)以某字符開頭的base值為i，第二個(gè)字符的字符序列碼依次為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 實(shí)現(xiàn)

假設(shè)，Tire里有n個(gè)節(jié)點(diǎn)，字符集大小為m，則DATrie的空間大小是n+cm，c是依賴于Trie稀疏程度的一個(gè)系數(shù)，而多路查找樹的空間大小是nm。

注意，這里的復(fù)雜度都是按離線算法（offline algorithm）計(jì)算的，即處理時(shí)已經(jīng)得到整個(gè)詞庫，在線算法（online algorithm）的空間復(fù)雜度還和單詞出現(xiàn)的順序有關(guān)，越有序的單詞順序空間占用越小。

查找算法的復(fù)雜度和被查找的字符串長度相關(guān)的，這個(gè)復(fù)雜度和多路查找樹是一樣的。

插入算法中，如果出現(xiàn)重分配的情況，我們要附加上掃描子節(jié)點(diǎn)的時(shí)間復(fù)雜度，還有新base值確定的算法復(fù)雜度，假如這兒我們都是用暴力算法（for循環(huán)掃描），那插入算法時(shí)間復(fù)雜度是O(nm + cm2)。

實(shí)際編碼過程中，DATrie代碼難度大過多路查找樹，主要是狀態(tài)的表示不如樹結(jié)構(gòu)那樣的清晰，下標(biāo)很容易搞混掉。

有個(gè)地方需要注意的是，base值正數(shù)表示起始偏移量，負(fù)數(shù)表示該狀態(tài)為終止態(tài)，所以在查找新base值時(shí)，要保證查到的值是正數(shù)。

如：空Trie狀態(tài)下，插入d時(shí)，因?yàn)榈谝粋€(gè)空地址是1，所以得到base=1-4=-3，這樣base正負(fù)的含義就被破壞了。

4、Trie樹的應(yīng)用

Trie是一種非常簡單高效的數(shù)據(jù)結(jié)構(gòu)，但有大量的應(yīng)用實(shí)例。

（1）、字符串檢索

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

①、給出N個(gè)單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請(qǐng)你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞。

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

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

Trie樹利用多個(gè)字符串的公共前綴來節(jié)省存儲(chǔ)空間，反之，當(dāng)我們把大量字符串存儲(chǔ)到一棵trie樹上時(shí)，我們可以快速得到某些字符串的公共前綴。

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

解決方案：首先對(duì)所有的串建立其對(duì)應(yīng)的字母樹，此時(shí)發(fā)現(xiàn)，對(duì)于兩個(gè)串的最長公共前綴的長度即它們所在結(jié)點(diǎn)的公共祖先個(gè)數(shù)，于是，問題就轉(zhuǎn)化為了離線（Offline）的最近公共祖先（LeastCommon Ancestor，簡稱LCA）問題。

而最近公共祖先問題同樣是一個(gè)經(jīng)典問題，可以用下面幾種方法：

①、利用并查集（Disjoint Set），可以采用采用經(jīng)典的Tarjan算法；

②、求出字母樹的歐拉序列（Euler Sequence）后，就可以轉(zhuǎn)為經(jīng)典的最小值查詢（Range Minimum Query，簡稱RMQ）問題

（3）、排序

Trie樹是一棵多叉樹，只要先序遍歷整棵樹，輸出相應(yīng)的字符串便是按字典序排序的結(jié)果。

例如：給你N個(gè)互不相同的僅由一個(gè)單詞構(gòu)成的英文名，讓你將它們按字典序從小到大排序輸出。

（4）、作為其他數(shù)據(jù)結(jié)構(gòu)和算法的輔助結(jié)構(gòu)

如后綴樹，AC自動(dòng)機(jī)等。

5、Trie樹復(fù)雜度分析

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

（2）、空間復(fù)雜度是26^n級(jí)別的，非常龐大（可采用雙數(shù)組實(shí)現(xiàn)改善）。

Trie樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，它在信息檢索，字符串匹配等領(lǐng)域有廣泛的應(yīng)用，同時(shí)，它也是很多算法和復(fù)雜數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，如后綴樹，AC自動(dòng)機(jī)等。

四、TrieMemory

Trie Memory是一種在內(nèi)存中存儲(chǔ)和檢索信息的方式，這種方式的優(yōu)點(diǎn)是訪問速度快，具有冗余存儲(chǔ)信息的優(yōu)點(diǎn)，主要的缺點(diǎn)是存儲(chǔ)空間利用率很低。

1、基本的Trie Memory模型

假設(shè)我們需要跟蹤一系列的單詞集合，這些集合是字母組成的序列，這些單詞序列有各種各樣的長度，我們必須記住的是這些字母組成的有限序列在這個(gè)集合中，總得來說，我們需要判斷一個(gè)序列是不是這個(gè)集合的成員。

剛開始trie僅僅是register組成的一個(gè)集合，除此之外還有兩個(gè)register，一個(gè)是α另一個(gè)是δ，每一個(gè)register都有cell來存儲(chǔ)整個(gè)字母表，如果我們要存儲(chǔ)“space”的話，每個(gè)register必須擁有27個(gè)cell。

每一個(gè)cell都有空間來存儲(chǔ)其它register在內(nèi)存中的地址，trie中的cell還沒有用來存儲(chǔ)信息，通常包含的是register α的地址信息。一個(gè)cell如果包含了非register α的register地址，則它表示存儲(chǔ)了信息，這些信息代表了這個(gè)cell的名稱，“A”表示A cell,“B”表示B cell。下一個(gè)register的地址在序列中。

下面用一個(gè)例子來說明，為了讓例子簡單些，我們使用字母表的前5個(gè)字符來表示整體。然后用?表示“space”，假設(shè)我們想存儲(chǔ)DAB,BAD,BADE,BE,BED,BEAD,CAB,CAD和A，接下來用圖來說明整個(gè)流程。

在圖中每一行代表一個(gè)register，每個(gè)register有6個(gè)cell，最后一行代表第三個(gè)特殊的register叫做portal register，是我們進(jìn)入系統(tǒng)內(nèi)存的通道它除了是入口外，也和其它register是一樣的，其它register是編號(hào)的，register α將會(huì)選擇它們，剛開始的時(shí)候register α是register 2。


基本Tire Memory模型

為了存儲(chǔ)DAB，我們引入地址“2”進(jìn)入portal register的D 單元格，然后我們移動(dòng)到register 2然后引入地址“3”到A單元格，然后我們進(jìn)入到register 3后把地址“4”放入單元格B，最后我們移動(dòng)到register 4 并且把地址“1”放入?單元，它是終止參數(shù)，至此DAB存儲(chǔ)結(jié)束。

然后我們轉(zhuǎn)到第二個(gè)單詞BAD，引入地址“5”進(jìn)入portal register的B單元格來表示字母B，然后到register 5的A單元格寫入地址“6”，再到register 6的D單元格寫入地址“7”，最后到register 7的?單元格寫入地址“1”。

當(dāng)我們開始存儲(chǔ)BADE時(shí)，我們發(fā)現(xiàn)B,A,D已經(jīng)在trie中了，因此我們沿著已經(jīng)存在的BAD的路徑到register 7然后引入地址“8”到單元格E中去，然后把地址“1”放入register 8的?單元。

2、Register的類型

在剛才提到的結(jié)構(gòu)中我們可以把register分為4種類型：

（1）、α(address) register來指向下一個(gè)存儲(chǔ)信息的地址。

（2）、δ(deletion) register

（3）、ν(next) register，下一步將要存儲(chǔ)的信息(在空內(nèi)存中，它是portal register)。

（4）、χ(exterior)類型χ是所有register中還沒有接受存儲(chǔ)信息并且沒有被指向?yàn)橄乱粋€(gè)存儲(chǔ)位置的register。

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

3、Trie的讀和寫

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

（1）、寫操作

①、把第i個(gè)參數(shù)字符傳入下一個(gè)register，如果是第一個(gè)字符，則是portal register。

②、選擇對(duì)應(yīng)字符串的的cell,如果第i個(gè)參數(shù)字符是字母表的第j個(gè)字符，選擇第j個(gè)cell。

③、檢測(cè)來自第i個(gè)單元的聯(lián)結(jié)。

④、如果這種聯(lián)結(jié)使得register α：

（a）、通過αregister把聯(lián)結(jié)投射到鏈接的頭部，這樣就可以存儲(chǔ)信息。

（b)、投射從αregister到鏈接頭部的聯(lián)結(jié)來創(chuàng)建一個(gè)“next”register(ν)。

（c)、最后，把所有的從ν發(fā)出來的聯(lián)結(jié)指向αregister。

⑤、如果源于第j個(gè)cell的聯(lián)結(jié)指向非 αregister的話，移動(dòng)到那個(gè)register去：

（a）、如果是第一個(gè)register，這參數(shù)是一個(gè)存儲(chǔ)集合的成員(結(jié)束流程)。

（b）、如果不是register 1的話，i加1并且轉(zhuǎn)到第二步去。

（2）、讀操作

使用相同的流程，但是不要使用投射，不要投射任何關(guān)系，如果聯(lián)結(jié)指向register 1，則這個(gè)參數(shù)是存儲(chǔ)集合的一個(gè)成員，如果任何點(diǎn)的聯(lián)結(jié)指向αregister，換句話說這個(gè)參數(shù)不是存儲(chǔ)集合的成員。

五、HASH索引

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

①、除留余數(shù)法(DivisionMethod)，H(key)=keyMOD p，p一般為質(zhì)數(shù)；

②、隨機(jī)數(shù)法(RandomMethod)，H(key)=random(key)，random為隨機(jī)函數(shù)；

③、平方取中法(MidsquareMethod)。

HASH索引結(jié)構(gòu)不需要額外的存儲(chǔ)空間，并且能夠在O(1)的時(shí)間復(fù)雜度下準(zhǔn)確定位到所查找的數(shù)據(jù)，將磁盤數(shù)據(jù)庫中的數(shù)據(jù)查找時(shí)間代價(jià)優(yōu)化至最小，Hash索引結(jié)構(gòu)由于以上優(yōu)點(diǎn)在磁盤數(shù)據(jù)庫中廣泛的運(yùn)用。

經(jīng)歷長久的研究，先后發(fā)展出了鏈接桶哈希(chainedbucket hash)，可擴(kuò)展哈希(extendible hash)、線性哈希(linearhash)和修正的線性哈希(modified linear hash)。

但是這些哈希算法雖然針對(duì)內(nèi)存數(shù)據(jù)庫進(jìn)行了少許優(yōu)化，但是與傳統(tǒng)數(shù)據(jù)庫中所用的哈希算法沒有明顯不同，到了2007年，KennethA. Ross提出了基于現(xiàn)代處理器的Hash預(yù)取算法將SIMD指令集融入到Hash算法中，才真正從內(nèi)存索引的角度改進(jìn)了哈希算法，提升數(shù)據(jù)組織的效率。

1、鏈接桶哈希

鏈接桶哈希是一個(gè)靜態(tài)的結(jié)構(gòu)，可用于內(nèi)存中與磁盤中，因?yàn)樗庆o態(tài)結(jié)構(gòu)，不用對(duì)數(shù)據(jù)進(jìn)行重組織，所以它速度很快。

但這也是它的缺陷，面對(duì)動(dòng)態(tài)數(shù)據(jù)，就顯得不合適了，因?yàn)殒溄油肮１仨氃谑褂弥爸拦１淼拇笮。@恰恰很難預(yù)測(cè)。

如果預(yù)測(cè)的表大小過小，其性能會(huì)大受影響；如果過大，空間浪費(fèi)較為嚴(yán)重，最好情況下，它只有一些空間的浪費(fèi)，用來存放指向下一個(gè)桶的指針。

2、可擴(kuò)展哈希

可擴(kuò)展哈希引入了目錄文件的概念，采用可隨數(shù)據(jù)增長的動(dòng)態(tài)哈希表，因此克服了鏈接桶哈希的缺陷，其哈希表大小不需要預(yù)先知道，一個(gè)哈希節(jié)點(diǎn)包含多個(gè)項(xiàng)，當(dāng)節(jié)點(diǎn)數(shù)量溢出時(shí)將其分裂為兩個(gè)節(jié)點(diǎn)，目錄按2的指數(shù)倍增長，當(dāng)一個(gè)節(jié)點(diǎn)裝滿而且到達(dá)了一個(gè)特定的目錄大小目錄就會(huì)倍增。

哈希函數(shù)為每個(gè)鍵計(jì)算一個(gè)K位的二進(jìn)制序列，桶的數(shù)量總是使用從序列第一位或者最后一位算起的若干位[]，但是可擴(kuò)展哈希的一個(gè)問題是任意一個(gè)節(jié)點(diǎn)都會(huì)引起目錄的分裂，當(dāng)哈希函數(shù)不夠隨機(jī)時(shí)，目錄很可能增長的很巨大。

3、線性哈希

線性哈希也使用動(dòng)態(tài)的哈希表，但是同可擴(kuò)展哈希有較大差別，線性哈希選擇桶數(shù)總是使存儲(chǔ)塊的平均記錄保持與容量成一個(gè)固定的比例，而且哈希桶不總是可以分裂，允許有溢出塊，當(dāng)插入的記錄沒有對(duì)應(yīng)的桶，將其哈希值首位改為0，再次插入，否則直接插入對(duì)應(yīng)桶或其溢出塊中，當(dāng)記錄數(shù)量比容量達(dá)到一個(gè)閾值，增加一個(gè)桶，再分配。

相對(duì)于可擴(kuò)展哈希，線性哈希的增長較為緩慢，重組織的次數(shù)和代價(jià)都較小，同時(shí)，線性散列不需要存放數(shù)據(jù)桶指針的專門目錄項(xiàng)，且能更自然的處理數(shù)據(jù)桶已滿的情況，允許更靈活的選擇桶分裂的時(shí)機(jī)。

4、修正的線性哈希

修正的線性哈希相對(duì)于線性哈希主要面向內(nèi)存環(huán)境，通過使用更大的連續(xù)節(jié)點(diǎn)替代目錄，普通的線性哈希由于有空節(jié)點(diǎn)而浪費(fèi)空間，而且，除非有一個(gè)巧妙的方案解決潛在的虛擬內(nèi)存映射機(jī)制問題，不然每次目錄增長時(shí)那個(gè)連續(xù)的節(jié)點(diǎn)都要被拷貝到一個(gè)更大的內(nèi)存塊。

修正的線性哈希采用跟可擴(kuò)展哈希一樣的目錄，除了目錄為線性增長的，鏈接的是單個(gè)項(xiàng)目的節(jié)點(diǎn)和分配內(nèi)存是從一個(gè)常規(guī)的內(nèi)存池。

這個(gè)算法節(jié)點(diǎn)分裂的準(zhǔn)則是基于性能，舉例來說，監(jiān)控哈希鏈的平均長度比監(jiān)控存儲(chǔ)利用率能夠更直接的控制平均搜索和更新時(shí)間。

5、Hash預(yù)取算法

Hash預(yù)取算法面向的是鍵和哈希值都是32位的場(chǎng)景，特地對(duì)內(nèi)存環(huán)境進(jìn)行了優(yōu)化，此算法使用乘法散列，這種方法十分普遍、計(jì)算高效，更重要的是適用于矢量，達(dá)到了一次計(jì)算多個(gè)哈希函數(shù)的目的。

針對(duì)現(xiàn)代處理器的SIMD架構(gòu)，將鍵值與哈希值共同放在一個(gè)指令當(dāng)中，達(dá)到大大減少指令數(shù)的目的，令每次所需的數(shù)據(jù)長度恰好等于L2的cacheline，大大降低了性能代價(jià)，在內(nèi)存環(huán)境中，大大提高了cache的性能。

億企邦點(diǎn)評(píng)：

索引是為檢索而存在的，如一些書籍的末尾就專門附有索引，指明了某個(gè)關(guān)鍵字在正文中的出現(xiàn)的頁碼位置，方便我們查找，但大多數(shù)的書籍只有目錄，目錄不是索引，只是書中內(nèi)容的排序，并不提供真正的檢索功能，可見建立索引要單獨(dú)占用空間；索引也并不是必須要建立的，它們只是為更好、更快的檢索和定位關(guān)鍵字而存在。