好的數據結構，對于檢索數據，插入數據的效率就會非常高。

常見的數據結構

B+樹

根節點和枝節點很簡單，分別記錄每個葉子節點的最小值，并用一個指針指向葉子節點。?
葉子節點里每個鍵值都指向真正的數據塊，每個葉子節點都有前指針和后指針，這是為了做范圍查詢時，葉子節點間可以直接跳轉，從而避免再去回溯至枝和根節點。?

特點：?
1、有n棵子樹的結點中含有n個關鍵字，每個關鍵字不保存數據，只用來索引，所有數據都保存在葉子節點。?
2、所有的葉子結點中包含了全部關鍵字的信息，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序鏈接。?
3、所有的非終端結點可以看成是索引部分，結點中僅含其子樹（根結點）中的最大（或最小）關鍵字。

缺點：?
通常數據量會很大，磁盤中的數據采用這種分頁形式的話，就會比較多。很有可能存儲的數據在兩個頁表當中不連續，相隔很遠，這種順序查詢的方式就會比較慢。?
B+樹最大的性能問題是會產生大量的隨機IO。隨著新數據的插入，葉子節點會慢慢分裂，邏輯上連續的葉子節點在物理上往往不連續，甚至分離的很遠，但做范圍查詢時，會產生大量讀隨機IO。?
對于大量的隨機寫也一樣，舉一個插入key跨度很大的例子，如7->1000->3->2000 … 新插入的數據存儲在磁盤上相隔很遠，會產生大量的隨機寫IO。從上面可以看出，低下的磁盤尋道速度嚴重影響性能。

LSM樹

?
為了更好的說明LSM樹的原理，下面舉個比較極端的例子：?
現在假設有1000個節點的隨機key，對于磁盤來說，肯定是把這1000個節點順序寫入磁盤最快，但是這樣一來，讀就悲劇了，因為key在磁盤中完全無序，每次讀取都要全掃描；

那么，為了讓讀性能盡量高，數據在磁盤中必須得有序，這就是B+樹的原理，但是寫就悲劇了，因為會產生大量的隨機IO，磁盤尋道速度跟不上。?
LSM樹本質上就是在讀寫之間取得平衡，和B+樹相比，它犧牲了部分讀性能，用來大幅提高寫性能。

它的原理是把一顆大樹拆分成N棵小樹， 它首先寫入到內存中（內存沒有尋道速度的問題，隨機寫的性能得到大幅提升），在內存中構建一顆有序小樹，隨著小樹越來越大，內存的小樹會flush到磁盤上。當讀時，由于不知道數據在哪棵小樹上，因此必須遍歷所有的小樹，但在每顆小樹內部數據是有序的。

HBase數據存儲格式

HBase引入了LSM樹的概念，即Log-Structured Merge-Trees。

HFile格式

---

?
HFile分為六個部分：?
Data Block 段?
—–保存表中的數據，這部分可以被壓縮。每一個數據塊由塊頭和一些KeyValue組成，key的值是嚴格按照順序存儲的。塊大小默認為64K（由建表時創建cf時指定或者HColumnDescriptor.setBlockSize(size)） ，這一部分可以壓縮存儲。?
在查詢數據時，是以數據塊為單位從硬盤load到內存。查找數據時，是順序的遍歷該塊中的keyValue對。

Meta Block 段 (可選的)?
–—保存用戶自定義的key-value對，可以被壓縮。 比如booleam filter就是存在元數據塊中的，該塊只保留value值，key值保存在元數據索引塊中。每一個元數據塊由塊頭和value值組成。可以快速判斷key是否都在這個HFile中。

File Info 段?
–—-HFile的元信息，不被壓縮，用戶也可以在這一部分添加自己的元信息。

Data Block Index 段?
—-–Data Block的索引，每條索引的key是被索引的block的第一條記錄的key（格式為：頭信息，（數據塊在文件中的偏移 + 數據塊長 + 數據塊的第一個key），（數據塊在文件中的偏移 + 數據塊長 + 數據塊的第一個key），……..）。?

Meta Block Index段 (可選的)?
–Meta Block的索引。 該塊組成格式同數據塊索引，只是某部分的意義不一樣。?

Trailer?
–—這一段是定長的。保存了每一段的偏移量，讀取一個HFile時，會首先讀取Trailer，Trailer**保存了每個段的起始位置**(段的Magic Number用來做安全check)，然后，DataBlock Index會被讀取到內存中，這樣，當檢索某個key時，不需要掃描整個HFile，而只需從內存中找到key所在的block，通過一次磁盤io將整個 block讀取到內存中，再找到需要的key。DataBlock Index采用LRU機制淘汰。?

說明如下：

1、 FileInfo Offset – FileInfo信息在HFile中的偏移。long(8字節)。?
2、 DataIndex Offset – 數據塊索引在HFile中的偏移。long(8字節)。?
3、 DataIndex Count – 數據塊索引的個數。int(4字節)。?
4、 MetaIndex Offset – 元數據索引塊在HFile中的偏移。long(8字節)。?
5、 MetaIndex Count – 元數據索引塊的個數。int(4字節)。?
6、 TotalUncompressedBytes – 未壓縮的數據塊部分的總大小。long(8字節)。?
7、 Entry Count – 數據塊中所有cell（key-value）的個數。int(4字節)?
8、 Compression Codec – 壓縮算法為enum類型，該值表示壓縮算法代碼。（LZO-0，GZ-1，NONE-2）,int(4字節)?
9、 Version – 版本信息。當前該版本值為1. int(4字節)。

HFile的Data Block，Meta Block通常采用壓縮方式存儲，壓縮之后可以大大減少網絡IO和磁盤IO，隨之而來的開銷當然是需要花費cpu進行壓縮和解壓縮。目標Hfile的壓縮支持兩種方式：Gzip，Lzo。

StoreFile格式

?
每個Strore又由一個memStore和0至多個StoreFile組成。?
StoreFile以HFile格式保存在HDFS上。

KeyValue對象格式

The KeyValue格式:

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">Keylength valuelength key <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">value</span></code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li></ul>

其中keylength和valuelength都是整型，表示長度。?
而key和value都是byte數據，key是有固定的數據，而value是raw data。Key的格式如下。

The Key format:

<code class="hljs erlang has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">rowlength <span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-title" style="box-sizing: border-box;">row</span> <span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(i.e., the rowkey)</span> <span class="hljs-title" style="box-sizing: border-box;">columnfamilylength</span> <span class="hljs-title" style="box-sizing: border-box;">columnfamily</span> <span class="hljs-title" style="box-sizing: border-box;">columnqualifier</span> <span class="hljs-title" style="box-sizing: border-box;">timestamp</span> <span class="hljs-title" style="box-sizing: border-box;">keytype</span></span></code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li></ul>

keytype有四種類型，分別是Put、Delete、 DeleteColumn和DeleteFamily。

總結

以上是生活随笔為你收集整理的HBase数据存储格式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。