萬字長文帶你詳解九大數據存儲引擎結構（上）

介紹

在存儲系統的設計中，存儲引擎屬于底層數據結構，直接決定了存儲系統所能夠提供的性能和功能。常見存儲算法結構涵蓋：哈希存儲，B 、B+、B*樹存儲，LSM樹存儲引擎，R樹，倒排索引，矩陣存儲，對象與塊，圖結構存儲等等。

哈希存儲引擎是哈希表的持久化實現，一般用于鍵值類型的存儲系統。而大多傳統關系型數據庫使用索引來輔助查找數據，用以加速對數據庫數據的訪問。考慮到經常需要范圍查找，因此其索引一般使用樹型結構。譬如MySQL、SQL Server、Oracle中，數據存儲與索引的基本結構是B-樹和B+樹。

主流的NoSQL數據庫則使用日志結構合并樹(Log-structured Merge Tree)來組織數據。LSM 樹存儲引擎和B樹一樣，支持增、刪、改、隨機讀取以及順序掃描。通過批量轉儲技術規避磁盤隨機寫入問題，極大地改善了磁盤的IO性能,被廣泛應用于后臺存儲系統，如Google Big table、Level DB，Facebook Cassandra系統，開源的HBase，Rocks dB等等。

一．哈希存儲

哈希存儲的基本思想是以關鍵字Key為自變量，通過一定的函數關系(散列函數或哈希函數），計算出對應函數值（哈希地址），以這個值作為數據元素的地址，并將數據元素存入到相應地址的存儲單元中。查找時再根據要查找的關鍵字采用同樣的函數計算出哈希地址，然后直接到相應的存儲單元中去取要找的數據元素。代表性的使用方包括Redis，Memcache，以及存儲系統Bitcask等。

基于內存中的Hash,支持隨機的增刪改查，讀寫的時間復雜度O(1)。但無法支持順序讀寫(指典型Hash，不包括如Redis的基于跳表的ZSet的其它功能),在不需要有序遍歷時，性能最優。

1.? 常用哈希函數

構造哈希函數的總的原則是盡可能將關鍵字集合空間均勻的映射到地址集合空間中，同時盡可能降低沖突發生的概率。

l? 除留余數法:H(Key)=key % p (p ≤ m)p最好選擇一個小于或等于m(哈希地址集合的個數)的某個最大素數。

l? 直接地址法: H(Key) =a * Key + b；“a，b”是常量。

l? 數字分析法

比如有一組key1=112233，key2=112633，key3=119033，分析數中間兩個數比較波動，其他數不變。那么取key的值就可以是 key1=22,key2=26,key3=90。

l? 平方取中法

l? 折疊法

比如key=135790，要求key是2位數的散列值。那么將key變為13+57+90=160，然后去掉高位“1”,此時key=60。

2.? 沖突處理方法

1)? 開放地址法

如果兩個數據元素的哈希值相同，則在哈希表中為后插入的數據元素另外選擇一個表項。當程序查找哈希表時，如果沒有在第一個對應的哈希表項中找到符合查找要求的數據元素，程序就會繼續往后查找，直到找到一個符合查找要求的數據元素，或者遇到一個空的表項。

①.線性探測法

這種方法在解決沖突時，依次探測下一個地址，直到有空的地址后插入，若整個空間都找遍仍然找不到空余的地址，產生溢出。Hi =( H(Key) + di ) % m? ( i = 1,2,3,...,k , k ≤ m-1 )

地址增量 di = 1,2,..., m-1, 其中 i 為探測次數

②.二次探測法

地址增量序列為: di= 1^2，-1^2，2^2，-2^2 ，...，q^2，-q^2 (q≤ m/2）

Python字典dict的實現是使用二次探查來解決沖突的。

③.雙哈希函數探測法

Hi =( H(Key) + i * RH(Key) ) % m? ( i=1,2,3,..., m-1)

H(Key) , RH(Key) 是兩個哈希函數，m為哈希表長度。先用第一個哈希函數對關鍵字計算哈希地址，一旦產生地址沖突，再用第二個函數確定移動的步長因子，最后通過步長因子序列由探測函數尋找空余的哈希地址。H1= (a +b) % m, H2 = (a + 2b) % m, ..., Hm-1= (a+ (m-1)*b) %m

2)? 鏈地址法

將哈希值相同的數據元素存放在一個鏈表中，在查找哈希表的過程中，當查找到這個鏈表時，必須采用線性查找方法。

Hash存儲示例

假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70),散列地址空間為HT[13]，采用除留余數法構造散列函數和線性探測法處理沖突。

二．B 樹存儲引擎

B樹存儲引擎是B樹的持久化實現，不僅支持單條記錄的增、刪、讀、改操作，還支持順序掃描（B+樹的葉子節點間的指針）。相比哈希存儲引擎，B樹存儲引擎不僅支持隨機讀取，還支持范圍掃描。Mysql的MyISAM和InnoDB支持B-樹索引,InnoDB還支持B+樹索引，Memory支持Hash。

1.? B-樹存儲

B-樹為一種多路平衡搜索樹，與紅黑樹最大的不同在于，B樹的結點可以有多個子節點，從幾個到幾千個。B樹與紅黑樹相似，一棵含n個結點的B樹的高度也為O(lgn)，但可能比一棵紅黑樹的高度小許多，因為它的分支因子比較大。所以B樹可在O(logn)時間內，實現各種如插入，刪除等動態集合操作。

B-樹的規則定義：

1)? ?定義任意非葉子節點最多可以有M個兒子節點；且M>2；

2)? ?則根節點的兒子數為：[2，M]；

3)? ?除根節點為的非葉子節點的兒子書為[M/2，M]；

4)? ?每個結點存放至少M/2-1(取上整)且至多M -1 個關鍵字；(至少為2)

5)? ?非葉子結點的關鍵字個數 = 指向子節點的指針書 -1；

6)? ?非葉子節點的關鍵字：K[1],K[2],K[3],…,K[M-1;且K[i] < K[i +1];

7)? ?非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；

8)? ?所有葉子結點位于同一層；

下圖是一個M為3的B-樹：

B-樹的搜索

從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為空，或已經是葉子結點；

B-樹的特性

關鍵字集合分布在整顆樹中,任何一個關鍵字出現且只出現在一個結點中；

所有結點都存儲數據，搜索有可能在非葉子結點結束；

搜索性能等價于在關鍵字全集內做一次二分查找,查詢時間復雜度不固定，與Key在樹中的位置有關，最好為O(1)；

非葉子節點存儲了data數據，導致數據量很大的時候，樹的層數可能會比較高，隨著數據量增加，IO次數的控制不如B+樹優秀。

MongoDB 存儲結構

MongoDB是聚合型數據庫，而B-樹恰好Key和data域聚合在一起，所有節點都有Data域，只要找到指定索引就可以進行訪問，無疑單次查詢平均快于MySql。

MongoDB并不是傳統的關系型數據庫，而是以Json格式作為存儲的NoSQL,目的就是高性能、高可用、易擴展。

2.? B+樹存儲

B樹在提高磁盤IO性能的同時并沒有解決元素遍歷的效率低下的問題。正是為了解決這個問題，B+樹應運而生。B+樹是對B樹的一種變形，本質還是多路平衡查找樹。B+樹只要遍歷葉子節點就可以實現整棵樹的遍歷。而且在數據庫中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作(或者說效率太低)。RDBMS需要B+樹用以減少尋道時間，順序訪問較快。

B+樹通常被用于數據庫和操作系統的文件系統中。像NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系統都在使用B+樹作為元數據索引。B+樹的特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間復雜度。B+樹元素為自底向上插入。

下圖是一棵高度為M=3的B+樹

B+樹上有兩個頭指針，一個指向根節點，另一個指向關鍵字最小的葉子節點，而且所有葉子節點(即數據節點)之間是一種鏈式環結構。因此可以對B+樹進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節點開始，進行隨機查找。

與普通B-樹相比，B+樹的非葉子節點只有索引，所有關鍵字都位于葉子節點，這樣會使樹節點的度比較大，而樹的高度就比較低，從而有利于提高查詢效率。并且葉子節點上的數據會形成有序鏈表。

主要優點如下：

結構比較扁平，高度低(一般不超過4層)，隨機尋道次數少；

有n棵子樹的結點中含有n個關鍵字，不用來保存數據，只用來索引。結點中僅含其子樹（根結點）中的最大（或最小）關鍵字。

數據存儲密度大，且都位于葉子節點，查詢穩定，遍歷方便；

葉子節點存放數值，按照值大小順序排序，形成有序鏈表，區間查詢轉化為順序讀，效率高。且所有葉子節點與根節點的距離相同，因此任何查詢效率都很相似。而B樹則必須通過中序遍歷才支持范圍查詢。

與二叉樹不同，B+樹的數據更新操作不從根節點開始，而從葉子節點開始，并且在更新過程中樹能以比較小的代價實現自平衡。

B+樹的缺點：

如果寫入的數據比較離散，那么尋找寫入位置時，子節點有很大可能性不會在內存中，最終產生大量隨機寫，性能下降。下圖說明了這一點。

B+樹在查詢過程中應該不會慢，但如B+樹已運行很長時間，寫入了很多數據，隨著葉子節點分裂，其對應的塊會不再順序存儲而變得分散,可能會導致邏輯上原本連續的數據實際上存放在不同的物理磁盤塊位置上，這時執行范圍查詢也會變成隨機讀，會導致較高的磁盤IO,效率降低。

譬如：數據更新或者插入完全無序時，如先插入0，后80000，然后200，然后666666，這樣跨度很大的數據時，由于不在一個磁盤塊中，就需先去查找到這個數據。數據非常離散，就意味著每次查找時，它的葉子節點很可能都不在內存中，此時就會出現性能的瓶頸。并且隨機寫產生的子樹的分裂等，產生很多的磁盤碎片，也是不太友好的一面。

可見B+樹在多讀少寫（相對而言）的情境下比較有優勢。當然，可用SSD來獲得成倍提升的讀寫速率，但成本相對較高。

B+樹的搜索

與B-樹基本相同，區別是B+樹只有達到葉子結點才命中(B-樹可在非葉子結點命中)，其性能也等價于在關鍵字全集做一次二分查找。

B+樹的特性

非葉子結點相當于是葉子結點的索引(稀疏索引)，葉子結點相當于是存儲(關鍵字)數據的數據層；B+樹的葉子結點都是相鏈的，因此對整棵樹的遍歷只需要一次線性遍歷葉子結點即可。而且由于數據順序排列并且相連，所以便于區間查找和搜索。而B-樹則需要進行每一層的遞歸遍歷。相鄰的元素可能在內存中不相鄰，所以緩存命中性沒有B+樹好。

比B-樹更適合實際應用中操作系統的文件索引和數據庫索引

1)? 磁盤讀寫代價更低

B+樹的內部結點并沒有指向關鍵字具體信息的指針。因此其內部結點相對B樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那么盤塊所能容納的關鍵字數量也越多。一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。

舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體信息指針2bytes。一棵9階B-tree(一個結點最多8個關鍵字)的內部結點需要2個盤快。而B+樹內部結點只需要1個盤快。當需要把內部結點讀入內存中的時候，B樹就比B+樹多一次盤塊查找時間。

2）查詢效率更加穩定

由于非葉子結點并不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。

MySQL InnoDB

InnoDB存儲引擎中頁大小為16KB，一般表的主鍵類型為INT(占用4字節)或long(8字節)，指針類型也一般為4或8個字節，也就是說一個頁(B+樹中的一個節點)中大概存儲16KB/(8B+8B)=1K個鍵值(K取估值為10^3)。即一個深度為3的B+樹索引可維護10^3 * 10^3 * 10^3=10億條記錄。

在數據庫中，B+樹的高度一般都在2~4層。MySql的InnoDB存儲引擎在設計時是將根節點常駐內存的，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作。

數據庫中的B+樹索引可以分為聚集索引(clustered index)和輔助索引(secondary index)。聚集索引的B+樹中的葉子節點存放的是整張表的行記錄數據。輔助索引與聚集索引的區別在于輔助索引的葉子節點并不包含行記錄的全部數據，而是存儲相應行數據的聚集索引鍵，即主鍵。當通過輔助索引來查詢數據時，InnoDB存儲引擎會遍歷輔助索引找到主鍵，然后再通過主鍵在聚集索引中找到完整的行記錄數據。

3.? B*樹存儲

B+樹的一種變形，在B+樹的基礎上將索引層以指針連接起來，使搜索取值更加快捷。如下圖(M=3)

http://image.huawei.com/tiny-lts/v1/images/ab7fb27100c2713ef8fe_803x467.jpg@900-0-90-f.jpg

相對B+樹的變化，如下：

B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3代替B+樹的1/2，將結點的最低利用率從1/2提高到2/3；

B+樹的分裂:當一個結點滿時分配一個新的結點，并將原結點中1/2的數據復制到新結點，最后在父結點中增加新結點的指針；B+樹的分裂只影響原結點和父結點，而不影響兄弟結點，所以它不需指向兄弟的指針；

B*樹的分裂:當一個結點滿時，如它的下一個兄弟結點未滿，那么將一部分數據移到兄弟結點中，再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字(因兄弟結點的關鍵字范圍改變),如兄弟也滿了,則在原結點與兄弟結點之間增加新結點,并各復制1/3數據到新結點,最后在父結點增加新結點的指針.

相對于B+樹，B*樹分配新結點的概率比B+樹要低，空間利用率、查詢速率也有所提高。

三．LSM樹存儲引擎

數據庫的數據大多存儲在磁盤上，無論是機械硬盤還是固態硬盤(SSD)，對磁盤數據的順序讀寫速度都遠高于隨機讀寫。大量的隨機寫，導致B樹在數據很大時，出現大量磁盤IO，速度越來越慢，基于B樹的索引結構是違背上述磁盤基本特點的—需較多的磁盤隨機讀寫。于是，基于日志結構的新型索引結構方法應運而生,主要思想是將磁盤看作一個大的日志，每次都將新的數據及其索引結構添加到日志的最末端，以實現對磁盤的順序操作，從而提高索引性能。

對海量存儲集群而言，LSM樹也是作為B+樹的替代方案而產生。當今很多主流DB都使用了LSM樹的存儲模型，包括LevelDB，HBase，Google BigTable，Cassandra，InfluxDB, RocksDB等。LSM樹通過盡可能減少寫磁盤次數，實際落地存儲的數據按key劃分，形成有序的不同文件；結合其“先內存更新后合并落盤”的機制，盡量達到順序寫磁盤，盡可能減少隨機寫；對于讀則需合并磁盤已有歷史數據和當前未落盤的駐于內存的更新。LSM樹存儲支持有序增刪改查，寫速度大幅提高，但隨機讀取數據時效率低。

LSM樹實際不是一棵樹，而是2個或者多個樹或類似樹的結構的集合。

下圖為包含2個結構的LSM樹

在LSM樹中，最低一級即最小的C0樹位于內存,而更高級的C1、C2...樹都位于磁盤里。數據會先寫入內存中的C0樹，當它的大小達到一定閾值之后，C0樹中的全部或部分數據就會刷入磁盤中的C1樹，如下圖所示。

由于內存讀寫速率比外存要快非常多，因此數據寫入C0樹的效率很高。且數據從內存刷入磁盤時是預排序的，也就是說，LSM樹將原本隨機寫操作轉化成了順序寫操作，寫性能大幅提升。不過，它的tradeoff就是犧牲了一部分讀性能，因為讀取時需將內存中數據和磁盤中的數據合并。總體上講這種權衡還是值得的,因為：

可以先讀取內存中C0樹的緩存數據。內存效率高且根據局部性原理，最近寫入的數據命中率也高。

寫入數據未刷到磁盤時不會占用磁盤的I/O，不會與讀取競爭。讀取操作就能取得更長的磁盤時間，變相地彌補了讀性能差距。

在實際應用中，為防止內存因斷電等原因丟失數據，寫入內存的數據同時會順序在磁盤上寫日志，類似于預寫日志(WAL)，這就是LSM這個詞中Log一詞的來歷。另外，如有多級樹，低級的樹在達到大小閾值后也會在磁盤中進行合并，如下圖所示。

1.? Leveldb/Rocksdb

基本描述

1)? 對數據，按key劃分為若干level，每個level對應若干文件，包括存在于內存中和落盤的。文件內key都有序，同級的各個文件之間一般也有序，level0對應于內存中的數據(0.sst)，后面依次是1、2、3、...的各級文件(默認到level6)。

2)? 寫時，先寫對應內存的最低level的文件，這也是快的一個原因。內存的數據也是被持久化的，達到一定大小后被合并到下一級文件落盤。

3)? 落盤后的各級文件也會定期進行排序加合并，合并后數據進入下一層level；這樣的寫入操作，大多數都是對一個頁順序的寫，或者申請新頁寫，而不再是隨機寫。

Rocksdb Compact

Compact是個很重要的步驟，下面是rocksdb的compact過程：

Rocksdb的各級文件組織形式：

各級的每個文件，內部都按key有序，除了內存對應的level0文件，內部文件之間也是按key有序；這樣查找一個key，很方便二分查找。

然后，當每一級的數據到達一定閾值時，會觸發排序歸并，簡單說，就是在兩個level的文件中，把key有重疊的部分，合并到高層level的文件里

這個在LSM樹里叫數據壓縮(compact)；

對于Rocksdb，除了內存level0到level1的compact，其他各級之間的compact可以并行；通常設置較小的level0到level1的compact閾值，加快這一層的compact。良好的歸并策略的配置，使數據盡可能集中在最高層(90%以上)，而不是中間層，這樣有利于compact的速度；另外，對于基于LSM樹的讀，需要在各級文件中二分查找，磁盤IO也不少，此外還需要關注level0里的對于這個key的操作，比較明顯的優化是，通過Bloomfilter略掉肯定不存在該key的文件，減少無謂查找；

2.? HBase LSM

說明：本小節需事先了解HBase的讀寫流程及MemStore。

MemStore作為列族級別的寫入和讀取緩存，它就是HBase中LSM樹的C0層。它未采用樹形結構來存儲，而是采用了跳表(一種替代自平衡BST二叉排序樹的結構)。MemStore Flush的過程，也就是LSM樹中C0層刷寫到C1層的過程，而LSM中的日志對應到HBase自然就是HLog了。

HBase讀寫流程簡圖

HFile就是LSM樹中的高層實現。從邏輯上來講，它是一棵滿的3層B+樹，從上到下的3層索引分別是Root index block、Intermediate index block和Leaf index block，對應到下面的Data block就是HFile的KeyValue結構。HFile V2索引結構的圖示如下：

HFile過多會影響讀寫性能，因此高層LSM樹的合并即對應HFile的合并(Compaction)操作。合并操作又分Minor和Major Compaction，由于Major Compaction涉及整個Region，對磁盤壓力很大,因此要盡量避免。

布隆過濾器(Bloom Filter)

是保存在內存中的一種數據結構，可用來驗證“某樣東西一定不存在或者可能存在”。由一個超長的二進制位數組和一系列的Hash函數組成，二進制位數組初始全部為0，當有元素加入集合時，這個元素會被一系列Hash函數計算映射出一系列的值，所有的值在位數組的偏移量處置為1。如需判斷某個元素是否存在于集合中，只需判斷該元素被Hash后的值在數組中的值，如果存在為0的則該元素一定不存在；如果全為1則可能存在，這種情況可能有誤判。

HBase為了提升LSM結構下的隨機讀性能而引入布隆過濾器(建表語句中可指定)，對應HFile中的Bloom index block，其結構圖如下。

通過布隆過濾器，HBase能以少量的空間代價，換來在讀取數據時非常快速地確定是否存在某條數據，效率進一步提升。

LSM-樹的這種結構非常有利于數據的快速寫入(理論上可接近磁盤順序寫速度），但不利于讀,因為理論上讀的時候可能需要同時從memtable和所有硬盤上的sstable中查詢數據，這樣顯然會對性能造成較大影響。為解決這個問題，LSM-樹采取以下主要相關措施。

定期將硬盤上小的sstable合并(Merge或Compaction)成大的sstable，以減少sstable的數量。且平時的數據更新刪除操作并不會更新原有的數據文件，只會將更新刪除操作加到當前的數據文件末端，只有在sstable合并的時候才會真正將重復的操作或更新去重、合并。

對每個sstable使用布隆過濾器,以加速對數據在該sstable的存在性進行判定,從而減少數據的總查詢時間。

SSTable(Sorted String Table)

當內存中的MemTable達到一定大小，需將MemTable轉儲(Dump)到磁盤中生成SSTable文件。由于數據同時存在MemTable和可能多個SSTable中，讀取操作需按從舊到新的時間順序合并SSTable和內存中的MemTable數據。

SSTable 中的數據按主鍵排序后存放在連續的數據塊(Block)中，塊之間也有序。接著，存放數據塊索引，由每個Block最后一行的主鍵組成，用于數據查詢中的Block定位。接著存放布隆過濾器和表格的Schema信息。最后存放固定大小的Trailer以及Trailer的偏移位置。

本質上看，SSTable是一個兩級索引結構：塊索引以及行索引。分為稀疏格式和稠密格式。對于稀疏格式，某些列可能存在也可能不存在，因此每一行只存儲包含實際值的列，每一列存儲的內容為：<列ID，列值>; 而稠密格式中每一行都需存儲所有列，每一列只需存儲列值，不需存儲列ID，列ID可從表格Schema中獲取。

3.? 圖庫ArangoDB LSM

ArangoDB采用RocksDB做底層存儲引擎，RocksDB使用LSM-Tree數據結構.

存儲的格式非常類似JSON，叫做VelocyPack格式的二進制格式存儲。

文檔被組織在集合中。

有兩種集合：文檔（V），邊集合（E）

邊集合也是以文檔形式存儲，但包含兩個特殊的屬性_from和_to，被用來創建在文檔和文檔之間創建關系

索引類型

·? ? ? ?Primary Index，默認索引，建立字段是_key或_id上，一個哈希索引

·? ? ? ?Edge Index，默認索引，建立在_from、_to上，哈希索引；不能用于范圍查詢、排序，弱于OrientDB

·? ? ? ?Hash Index，自建

·? ? ? ?Skiplist Index，有序索引，

用于快速查找具有特定屬性值的文檔，范圍查詢以及按索引排序，順序返回文檔。

用于查找，范圍查詢和排序。補全范圍查詢的缺點。

·? ? ? ?Persistent Index，RocksDB的索引。

持久性索引是具有持久性的排序索引。當存儲或更新文檔時，索引條目將寫入磁盤。

使用持久性索引可能會減少集合加載時間。

·? ? ? Geo Index，可以在集合中的一個或多個屬性上創建其他地理索引。

·? ? ? Fulltext Index，全文索引

四．R樹的存儲結構

R樹是B樹在高維空間的擴展，是一棵平衡樹。每個R樹的葉子結點包含了多個指向不同數據的指針，這些數據可以是存放在硬盤中，也可存在內存中。根據R樹的這種數據結構，當需進行一個高維空間查詢時，只需要遍歷少數幾個葉子結點所包含的指針，查看這些指針指向的數據是否滿足即可。這種方式使得不必遍歷所有數據即可獲得答案，效率顯著提高。

下圖是R樹的一個簡單實例：

R樹運用空間分割理念，采用一種稱為MBR(Minimal Bounding Rectangle)的方法，在此譯作“最小邊界矩形”。從葉子結點開始用矩形將空間框起來，結點越往上，框住的空間就越大，以此對空間進行分割。

以二維空間舉例,下圖是Guttman論文中的一幅圖：

1)? ?首先假設所有數據都是二維空間下的點，圖中僅僅標志了R8區域中的數據，也就是那個shape of data object。別把那一塊不規則圖形看成一個數據，把它看作是多個數據圍成的一個區域。為了實現R樹結構，用一個最小邊界矩形恰好框住這個不規則區域，這樣就構造出了一個區域：R8。R8的特點很明顯，就是正好框住所有在此區域中的數據。其他實線包圍住的區域，如R9，R10，R12等都是同樣道理。這樣一共得到了12個最最基本的最小矩形。這些矩形都將被存儲在子結點中。

2)? ?下一步操作就是進行高一層次的處理,發現R8，R9，R10三個矩形距離最為靠近，因此就可以用一個更大的矩形R3恰好框住這3個矩形。

3)? ?同樣，R15，R16被R6恰好框住，R11，R12被R4恰好框住，等等。所有最基本的最小邊界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住這些矩形。

用地圖和餐廳的例子來解釋，就是所有的數據都是餐廳所對應的地點，先把相鄰的餐廳劃分到同一塊區域，劃分好所有餐廳之后，再把鄰近的區域劃分到更大的區域，劃分完畢后再次進行更高層次的劃分，直到劃分到只剩下兩個最大的區域為止。要查找的時候就方便了。

然后就可以把這些大大小小的矩形存入R樹中。根結點存放的是兩個最大的矩形，這兩個最大的矩形框住了所有的剩余的矩形，當然也就框住了所有的數據。下一層的結點存放了次大的矩形，這些矩形縮小了范圍。每個葉子結點都是存放的最小的矩形，這些矩形中可能包含有n個數據。

查詢特定的數據

以餐廳為例，假設查詢廣州市天河區天河城附近一公里的所有餐廳地址

1)? ?打開地圖(即整個R樹)，先選擇國內還是國外(根結點);

2)? ?然后選擇華南地區(對應第一層結點)，選擇廣州市(對應第二層結點);

3)? ?再選擇天河區（對應第三層結點）;

4)? ?最后選擇天河城所在的那個區域(對應葉子結點，存放有最小矩形)，遍歷所有在此區域內的結點，看是否滿足要求即可。

其實R樹的查找規則跟查地圖很像，對應下圖：

一棵R樹滿足如下性質：

1)? ?除非它是根結點之外，所有葉子結點包含有m至M個記錄索引(條目)。作為根結點的葉子結點所具有的記錄個數可以少于m。通常，m=M/2。

2)? ?對于所有在葉子中存儲的記錄(條目)，I是最小的可以在空間中完全覆蓋這些記錄所代表的點的矩形(此處所說“矩形”是可擴展到高維空間)。

3)? ?每一個非葉子結點擁有m至M個孩子結點，除非它是根結點。

4)? ?對于在非葉子結點上的每一個條目，i是最小的可在空間上完全覆蓋這些條目所代表的店的矩形(同性質2)

5)? ?所有葉子結點都位于同一層，因此R樹為平衡樹。

說明：

葉子結點的結構，數據形式為: (I, tuple-identifier)，tuple-identifier表示的是一個存放于數據庫中的tuple，也就是一條記錄，是n維的。I是一個n維空間的矩形，并可恰好框住這個葉子結點中所有記錄代表的n維空間中的點。I=(I0,I1,…,In-1)。

R樹是一種能夠有效進行高維空間搜索的數據結構，已被廣泛應用在各種數據庫及其相關的應用中。但R樹的處理也具局限性，它的最佳應用范圍是處理2至6維的數據，更高維的存儲會變得非常復雜，這樣就不適用。近年來，R樹也出現了很多變體，R*樹就是其中的一種。這些變體提升了R樹的性能，如需更多了解，可以參考相關文獻。

應用示例

地理圍欄(Geo-fencing)是LBS(Location Based Services)的一種應用，就是用一個虛擬的柵欄圍出一個虛擬地理邊界，當手機進入、離開某個特定地理區域，或在該區域內活動時，手機可以接收自動通知和警告。譬如，假設地圖上有三個商場，當用戶進入某個商場的時候，手機自動收到相應商場發送的優惠券push消息。地理圍欄應用非常廣泛，當今移動互聯網主要app如美團、大眾點評、手淘等都可看到其應用身影。

----------未完，請閱讀（下）-------

萬字長文帶你詳解九大數據存儲引擎結構（下）

MySQL 存儲 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。