數(shù)據(jù)庫(kù)原理與應(yīng)用 課件 第7章 數(shù)據(jù)組織與存儲(chǔ)管理

第7章數(shù)據(jù)組織與存儲(chǔ)管理7.1B+樹(shù)7.2跳躍表7.3LSM樹(shù)7.4布隆過(guò)濾器第7章數(shù)據(jù)組織與存儲(chǔ)管理三種基本數(shù)據(jù)存儲(chǔ)引擎？第7章數(shù)據(jù)組織與存儲(chǔ)管理1、哈希存儲(chǔ)引擎（高效隨機(jī)查找）2、B樹(shù)存儲(chǔ)引擎（高效范圍查找）3、LSM樹(shù)存儲(chǔ)引擎第7章數(shù)據(jù)組織與存儲(chǔ)管理如果需要滿足下述要求，需要怎樣的數(shù)據(jù)結(jié)構(gòu)：寫(xiě)多讀少能夠高速寫(xiě)入大量數(shù)據(jù)能夠高速讀取大量數(shù)據(jù)著名計(jì)算機(jī)科學(xué)家N.Wirth說(shuō)過(guò)：程序=算法+數(shù)據(jù)結(jié)構(gòu)HBase代碼行數(shù)超過(guò)150萬(wàn)，仍然是算法和數(shù)據(jù)結(jié)構(gòu)組成HBase的一個(gè)列族本質(zhì)上就是一棵LSM樹(shù)（Log-StructuredMergeTree）。該樹(shù)分為內(nèi)存部分和磁盤(pán)部分內(nèi)存部分是一個(gè)維護(hù)有序數(shù)據(jù)集合的數(shù)據(jù)結(jié)構(gòu)，可以選擇平衡二叉樹(shù)、紅黑樹(shù)、跳躍表等維護(hù)有序數(shù)據(jù)集合的結(jié)構(gòu)。HBase選擇了跳躍表為了避免不必要的IO耗時(shí)，HBase選擇了布隆過(guò)濾器，用來(lái)快速判斷key值是否存儲(chǔ)在當(dāng)前塊中7.1B+樹(shù)7.1B+樹(shù)B+樹(shù)可以定義一個(gè)m值作為預(yù)定范圍，即m路(階)B+樹(shù)。一個(gè)節(jié)點(diǎn)的結(jié)構(gòu)是：（K1，P1，K2，...Km-1,Pm),其中P為指向子節(jié)點(diǎn)（子樹(shù)）的指針，K為索引鍵值。對(duì)于根節(jié)點(diǎn)，如果它本身不是葉子節(jié)點(diǎn)，則至少擁有1個(gè)關(guān)鍵字，即至少有2個(gè)子樹(shù)除了根節(jié)點(diǎn)，非葉子節(jié)點(diǎn)至少擁有

個(gè)指針；葉子節(jié)點(diǎn)最少

個(gè)索引鍵值除了根節(jié)點(diǎn)，所有節(jié)點(diǎn)最多包含

個(gè)子樹(shù)，即

個(gè)索引鍵值7.1B+樹(shù)非葉子節(jié)點(diǎn)不保存數(shù)據(jù)，只保存關(guān)鍵字用作索引，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)中。非葉子節(jié)點(diǎn)有若干子樹(shù)指針，如果非葉子節(jié)點(diǎn)索引鍵值為k1,k2,…km，那么第一個(gè)子樹(shù)索引鍵值判斷條件為小于k1，第二個(gè)為大于等于k1而小于k2，以此類推，最后一個(gè)為大于等于km，總共可以劃分出m個(gè)區(qū)間，即可以有m個(gè)分支。7.1B+樹(shù)

插入鍵值7的情況（父節(jié)點(diǎn)無(wú)分裂)1.插入操作7.1B+樹(shù)圖中給出了一個(gè)節(jié)點(diǎn)的分裂情況：向樹(shù)中插入鍵值7。首先通過(guò)查找算法定位插入的位置，在葉節(jié)點(diǎn)的6和9兩個(gè)鍵值之間插入7。設(shè)當(dāng)前葉節(jié)點(diǎn)的階數(shù)為4，每個(gè)葉節(jié)點(diǎn)最多可以存放3個(gè)鍵值，因此需要進(jìn)行節(jié)點(diǎn)的分裂操作，右圖所示。以位置為m/2位置的鍵值，即6為分裂點(diǎn)，5和6保留在當(dāng)前節(jié)點(diǎn)，7和9傳輸?shù)叫聞?chuàng)建的節(jié)點(diǎn)中，同時(shí)將鍵值7提升至父節(jié)點(diǎn)中，增加指向父節(jié)點(diǎn)的指針和同級(jí)節(jié)點(diǎn)的指針。1.插入操作7.1B+樹(shù)插入鍵值2的情況(父節(jié)點(diǎn)有分裂）1.插入操作7.1B+樹(shù)圖中給出了一個(gè)非葉節(jié)點(diǎn)的分裂情況：若向圖中的B+樹(shù)中插入鍵值2時(shí)，在包含（1，3，4）的葉子節(jié)點(diǎn)中插入該值以后，該節(jié)點(diǎn)超過(guò)了最大鍵值個(gè)數(shù)3，因此需要進(jìn)行分裂。選擇鍵值2處作為分裂點(diǎn)，將鍵值3提升至父節(jié)點(diǎn)，并將（1，3，4）節(jié)點(diǎn)分裂成兩部分，1和2保留在原始節(jié)點(diǎn)中，3和4放在新創(chuàng)建的節(jié)點(diǎn)中。之后，由于非葉節(jié)點(diǎn)（5，7，11）在插入鍵值3后，超過(guò)了最大鍵值個(gè)數(shù)，需要再次進(jìn)行分裂，提升鍵值7，創(chuàng)建新的根節(jié)點(diǎn)，樹(shù)的高度由2變?yōu)?，此處因?yàn)槭欠侨~節(jié)點(diǎn)分裂，所以新創(chuàng)建的節(jié)點(diǎn)（11）中不用重復(fù)保留鍵值7。最后，增加新節(jié)點(diǎn)到父節(jié)點(diǎn)的指針。7.1B+樹(shù)刪除鍵值2的情況（合并）2.刪除操作7.1B+樹(shù)刪除鍵值9的情況（重新分配）2.刪除操作思考題請(qǐng)自己查找B+樹(shù)的構(gòu)造、插入、刪除、查詢等操作的代碼，搞懂執(zhí)行過(guò)程。7.2跳躍表跳躍表（skipList）是一種能高效實(shí)現(xiàn)插入、刪除、查找的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，這些操作的期望復(fù)雜度都是O(logN).這種數(shù)據(jù)結(jié)構(gòu)是由WilliamPugh發(fā)明的，最早出現(xiàn)于他在1990年發(fā)表的論文《SkipLists:AProbabilisticAlternativetoBalancedTrees》。跳躍表被廣泛地使用在KV數(shù)據(jù)庫(kù)中，如Redis、LevelDB、HBase都是把跳躍表作為一種維護(hù)有序數(shù)據(jù)集合的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。7.2

跳躍表鏈表的復(fù)雜度是多少？O(n)7.2跳躍表每條鏈表都是有序的每條鏈表都有兩個(gè)元素：正無(wú)窮大（+∞）和負(fù)無(wú)窮大（-∞），分別表示鏈表的頭部和尾部從上至下，上層鏈表元素集合是下層鏈表元素集合的子集跳表的高度定義為水平鏈表的層數(shù)1.定義7.2跳躍表(1)由很多層結(jié)構(gòu)組成，level是通過(guò)一定的概率隨機(jī)產(chǎn)生的；(2)每一層都是一個(gè)有序的鏈表，默認(rèn)是升序；(3)最底層(Level1)的鏈表包含所有元素；(4)如果一個(gè)元素出現(xiàn)在Leveli的鏈表中，則它在Leveli之下的

鏈表也都會(huì)出現(xiàn)；

(5)每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。2.性質(zhì)7.2跳躍表以左上角元素（設(shè)為currentNode）作為起點(diǎn)如果發(fā)現(xiàn)currentNode后繼節(jié)點(diǎn)的值小于等于待查詢值，則沿著這條鏈表向后查詢，否則，切換到當(dāng)前節(jié)點(diǎn)的下一層鏈表。繼續(xù)查找，直到找到待查詢值為止（或者currentNode為空節(jié)點(diǎn)）。查找元素15的流程7.2跳躍表每?jī)蓚€(gè)結(jié)點(diǎn)會(huì)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)，那第一級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是n/2，第二級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是n/4，第三級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是n/8，依次類推，也就是說(shuō)，那第k級(jí)索引結(jié)點(diǎn)的個(gè)數(shù)就是n/(2^k).假設(shè)索引有k級(jí)，最高級(jí)的索引有2個(gè)結(jié)點(diǎn)。通過(guò)上面的公式，我們可以得到n/(2^k)=2，從而求得k=logn-1,如果包含原始鏈表層，整個(gè)跳表高度是logn.如果在跳表中每一層索引需要遍歷m個(gè)節(jié)點(diǎn)，則在跳表中查詢一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度為O(m*logn).查詢的時(shí)間復(fù)雜度7.2跳躍表那這個(gè)m的值是多少呢？按照前面這種索引結(jié)構(gòu)，我們每一級(jí)索引都最多只需要遍歷3個(gè)結(jié)點(diǎn)，也就是說(shuō)m=3所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時(shí)間復(fù)雜度就是O(logn)也就是這些多級(jí)索引把一個(gè)單鏈表分成了一個(gè)個(gè)的區(qū)間段，每次索引層的查找都確定了一個(gè)小的區(qū)間段，于是就提高了效率，但是卻浪費(fèi)了建立索引需要的空間，這就是空間換時(shí)間的思路7.2跳躍表假設(shè)單鏈表的長(zhǎng)度為n，第一級(jí)索引大概n/2個(gè)節(jié)點(diǎn)，第二級(jí)索引大概n/4個(gè)節(jié)點(diǎn)，第三級(jí)索引大概n/8個(gè)節(jié)點(diǎn)。依次類推直到剩下2個(gè)索引節(jié)點(diǎn)。于是組成了一個(gè)等比數(shù)列：n/2、n/4、n/8、.........8、4、2.這些級(jí)的索引加起來(lái)等于n-2,所以跳表的空間復(fù)雜度O(n),即長(zhǎng)度為n單鏈表在每隔兩個(gè)節(jié)點(diǎn)抽取一個(gè)索引節(jié)點(diǎn)時(shí)，組成的跳表需要額外n個(gè)節(jié)點(diǎn)來(lái)存儲(chǔ)索引。空間復(fù)雜度7.2跳躍表如果每隔三個(gè)節(jié)點(diǎn)抽取一個(gè)索引節(jié)點(diǎn)，那么第一層索引節(jié)點(diǎn)數(shù)大概為n/3,第二層索引的節(jié)點(diǎn)數(shù)大概為n/9，依次類推假設(shè)最后一層索引節(jié)點(diǎn)數(shù)為1，則組成的等比數(shù)列是n/3、n/9、n/27、.......9、3、1.加起來(lái)的和為(n-1)/2,空間占用差不多減少了一半的存儲(chǔ)。實(shí)際上索引占用空間相比原始單鏈表本身節(jié)點(diǎn)小巫見(jiàn)大巫了，畢竟一半節(jié)點(diǎn)中存儲(chǔ)的是對(duì)象，而索引中只是id,占不了多少空間。如何降低空間復(fù)雜度7.2跳躍表1、給定一個(gè)有序的鏈表。

2、選擇鏈表中最大和最小的元素，然后從其他元素中按照一定算法（隨機(jī)）隨即選出一些元素，將這些元素組成有序鏈表。這個(gè)新的鏈表稱為一層，原鏈表稱為其下一層。

3、為剛選出的每個(gè)元素添加一個(gè)指針域，這個(gè)指針指向下一層中值同自己相等的元素。Top指針指向該層首元素

4、重復(fù)2、3步，直到不再能選擇出除最大最小元素以外的元素。跳躍表的構(gòu)建7.2跳躍表第一步，需要按照查找流程找到待插入元素的前驅(qū)節(jié)點(diǎn)9第二步，在鏈表中插入節(jié)點(diǎn)10第三步，按照如下隨機(jī)算法生成一個(gè)高度值：插入操作插入元素10的流程7.2跳躍表//p是一個(gè)(0,1)之間的常數(shù)，一般取p=1/4或1/2PublicintrandomHeight(doublep){intheight=0;while{random.nextDouble()<preturnheight+1;}random.nextDouble()返回一個(gè)大于或等于0.0且小于1.0的隨機(jī)浮點(diǎn)數(shù)。隨機(jī)函數(shù)的選擇是非常有講究的，從概率上講，能夠保證跳表的索引大小和數(shù)據(jù)大小平衡性，不至于性能的過(guò)度退化。至于隨機(jī)函數(shù)的選擇，見(jiàn)上面的代碼實(shí)現(xiàn)過(guò)程，而且實(shí)現(xiàn)過(guò)程并不是重點(diǎn)，掌握思想即可。插入操作7.2跳躍表第四步，將待插入節(jié)點(diǎn)按照高度值生成一個(gè)垂直節(jié)點(diǎn)（這個(gè)節(jié)點(diǎn)的層數(shù)等于高度值），之后插入到跳躍表的

多條鏈表中。假設(shè)height=randomHeight(p)，這里分為

兩種情況：

如果height大于跳躍表的高度,則跳躍表的高度被提升為height，同時(shí)需要更新頭部節(jié)點(diǎn)和尾部節(jié)點(diǎn)的指針指向。如果height小于等于跳躍表的高度，則只需要更新待插入元素前驅(qū)和后繼的指針指向。插入操作7.2跳躍表7.2跳躍表7.2跳躍表刪除操作7.3LSM樹(shù)LSM樹(shù)本質(zhì)上和B+樹(shù)一樣，是一種磁盤(pán)數(shù)據(jù)的索引結(jié)構(gòu)。和B+樹(shù)不同的是，LSM樹(shù)的索引對(duì)寫(xiě)入請(qǐng)求更友好。因?yàn)闊o(wú)論是何種寫(xiě)入請(qǐng)求，LSM樹(shù)都會(huì)將寫(xiě)入操作理解為一次順序?qū)懀鳫DFS擅長(zhǎng)順序?qū)懭耄℉DFS不支持隨機(jī)寫(xiě)入），因此，基于HDFS實(shí)現(xiàn)的HBase采用LSM樹(shù)作為索引是一種合適的選擇。7.3LSM樹(shù)LSM樹(shù)的索引結(jié)構(gòu)ConcurrentSkipListMemStorehfilehfilehfilehfilehfileflushMemoryDisk7.3LSM樹(shù)LSM樹(shù)的索引有兩部分構(gòu)成：內(nèi)存部分和磁盤(pán)部分。內(nèi)存部分是一個(gè)SkipList（跳表），Key就是HBase中KeyValue的Key的構(gòu)成（rowkey,family,Qualifier,Timestamp,Type)Data數(shù)據(jù)塊Block’TypeCell（KeyValue）CellCell……BlockType:塊的類型Cell：KeyValue鍵值對(duì)KeyLenValueLenRowLenRowCFLenCFColTimeStampKeyTypeValue7.3LSM樹(shù)一般來(lái)說(shuō)，LSM中存儲(chǔ)的是多個(gè)KeyValue組成的集合，每個(gè)KeyValue都會(huì)用一個(gè)字節(jié)數(shù)組來(lái)表示。字節(jié)數(shù)組設(shè)計(jì)如下：KeyValue存儲(chǔ)格式KeyLenValLenRowkeyLenRowkeyBytesfamilyLenfamilyBytesqualifierBytesTimestamp(8B)Type(1B)valueBytes(1B)qualifierBytes:存儲(chǔ)Qualifier的二進(jìn)制內(nèi)容。注意：HBase并沒(méi)有單獨(dú)分配字節(jié)用來(lái)存儲(chǔ)qualifierLen，但可以計(jì)算出來(lái)qualifierLen=keyLen-rowkeyLen-familyLen-8B-1B7.3LSM樹(shù)type:表示這個(gè)keyValue操作的類型，HBase內(nèi)由Put、Delete、DeleteColumn、DeleteFamily等。該字段表明了LSM樹(shù)內(nèi)存的不只是數(shù)據(jù)，而是每一次操作記錄.Value部分直接存儲(chǔ)在valueBytes中，所以，字節(jié)數(shù)組主要是key部分的設(shè)計(jì)。1.KeyValue存儲(chǔ)格式keyLen(4B)valLen(4B)rowkeyLen(2B)rowkeyBytesfamilyLen(1B)familyBytesqualifierBytestimestamp(8B)type(1B)valueBytes(1B)7.3LSM樹(shù)LSM樹(shù)中KeyValue的Key部分，有3個(gè)字段必不可少：RowKey的二進(jìn)制內(nèi)容一個(gè)表示版本號(hào)的64位long值，在HBase中對(duì)應(yīng)timestamp；這個(gè)版本號(hào)通常表示數(shù)據(jù)的寫(xiě)入先后順序，版本號(hào)越大的數(shù)據(jù)，越優(yōu)先被用戶讀取。Type,表示這個(gè)KeyValue的操作類型。本質(zhì)上，LSM存儲(chǔ)的并非只有數(shù)據(jù)，而是操作記錄。這正是LSM（LogStructuredMerge-Tree）中l(wèi)og的含義。7.3LSM樹(shù)LSM樹(shù)的索引結(jié)構(gòu)ConcurrentSkipListMemStorehfilehfilehfilehfilehfileflushMemoryDiskCompaction7.3LSM樹(shù)為了避免flush操作影響寫(xiě)入性能，會(huì)先把當(dāng)前寫(xiě)入的MemStore設(shè)為Snapshot，不再容許新的寫(xiě)入操作寫(xiě)入這個(gè)MemStore，另外一個(gè)內(nèi)存空間作為MemStore。Snapshot的MemStore寫(xiě)入完畢，對(duì)應(yīng)內(nèi)存空間就可釋放。因此，可以通過(guò)兩個(gè)MemStore來(lái)實(shí)現(xiàn)穩(wěn)定的寫(xiě)入性能。整個(gè)寫(xiě)入過(guò)程，LSM樹(shù)都是append操作（磁盤(pán)順序?qū)懭耄?，沒(méi)有seek+write（磁盤(pán)隨機(jī)寫(xiě)入）。LSM樹(shù)是一種對(duì)寫(xiě)入極為友好的索引結(jié)構(gòu)。7.3LSM樹(shù)磁盤(pán)上的數(shù)據(jù)文件隨著數(shù)據(jù)的增加不斷增多，對(duì)用戶的讀取請(qǐng)求，需要進(jìn)行大量的多路歸并操作。需要將key值相同的數(shù)據(jù)全局綜合起來(lái)(Compaction)，選擇合適的版本返回給用戶。/u010761477/article/details/898863397.3LSM樹(shù)compaction（異步）操作分為兩種類型：majorcompact：不宜頻繁使用優(yōu)點(diǎn)：合并之后只有一個(gè)文件，讀取性能最高缺點(diǎn)：合并所有的文件需要很長(zhǎng)時(shí)間，消耗大量帶寬。minorcompact優(yōu)點(diǎn)：局部的compact操作，少了IO減少文件個(gè)數(shù)，提升讀取性能缺點(diǎn)：全局操作，無(wú)法在合并過(guò)程中完成。7.3LSM樹(shù)寫(xiě)入操作轉(zhuǎn)換為磁盤(pán)的順序?qū)懭?，極大提高了寫(xiě)入的效率。對(duì)讀取操作不十分友好設(shè)計(jì)了異步的compaction操作，提高讀取性能HBase選擇LSM樹(shù)這種索引結(jié)構(gòu)是最合適的總結(jié)7.4布隆過(guò)濾器在使用新聞客戶端看新聞時(shí)，它會(huì)給我們不停地推薦新的內(nèi)容，它每次推薦時(shí)要去重，去掉那些已經(jīng)看過(guò)的內(nèi)容。當(dāng)推薦系統(tǒng)推薦新聞時(shí)會(huì)從每個(gè)用戶的歷史記錄里進(jìn)行篩選，只將不在歷史記錄中的新聞推薦給用戶。如何快速查找呢？將哈希與位圖結(jié)合，即布隆過(guò)濾器7.4布隆過(guò)濾器如何高效判斷元素w是否存在于集合A中？哈希表對(duì)于小數(shù)據(jù)集是比較有效的解決策略布隆過(guò)濾器由一個(gè)長(zhǎng)度為N的0，1數(shù)組組成。首先將數(shù)組array每個(gè)元素都設(shè)置為0.對(duì)集合A中的每個(gè)元素w,做K次哈希，第i次哈希值對(duì)N取模得到一個(gè)index(i)，index(i)=HASH_i(w)%N，將array數(shù)組中的array[index(i)]置為1。7.4布隆過(guò)濾器舉例A={x,y,z},M=18,K

=3

初始化array=000000000000000000對(duì)元素x，HASH_0(x)%M=1,HASH_1(x)%M=5,HASH_2(x)%M=1301234567891011121314151617010001000000010000012345678910111213141516177.4布隆過(guò)濾器對(duì)元素y，HASH_0(y)%M=4,HASH_1(y)%M=11,HASH_2(y)%M=16010011000001010010012345678910111213141516