HFile索引結構解析
V2版本Index Block有兩類：Root Index Block和NonRoot Index Block，其中NonRoot Index Block又分為Intermediate Index Block和Leaf Index Block兩種。HFile中索引結構類似于一棵樹，Root Index Block表示索引數根節點，Intermediate Index Block表示中間節點，Leaf Index block表示葉子節點，葉子節點直接指向實際資料塊。
HFile中除了Data Block需要索引之外，上一篇文章提到過Bloom Block也需要索引，索引結構實際上就是采用了single-level結構，文中Bloom Index Block就是一種Root Index Block。
對于Data Block，由于HFile剛開始資料量較小，索引采用single-level結構，隻有Root Index一層索引，直接指向資料塊。當資料量慢慢變大，Root Index Block滿了之後，索引就會變為mutil-level結構，由一層索引變為兩層，根節點指向葉子節點，葉子節點指向實際資料塊。如果資料量再變大，索引層級就會變為三層。
下面就針對Root index Block和NonRoot index Block兩種結構進行解析，因為Root Index Block已經在上面一篇文章中分析過，此處簡單帶過，重點介紹NonRoot Index Block結構（InterMediate Index Block和Ieaf Index Block在記憶體和磁盤中存儲格式相同，都為NonRoot Index Block格式）。
Root Index Block
Root Index Block表示索引樹根節點索引塊，可以作為bloom的直接索引，也可以作為data索引的根索引。而且對于single-level和mutil-level兩種索引結構對應的Root Index Block略有不同，本文以mutil-level索引結構為例進行分析（single-level索引結構是mutual-level的一種簡化場景），在記憶體和磁盤中的格式如下圖所示：
其中Index Entry表示具體的索引對象，每個索引對象由3個字段組成，Block Offset表示索引指向資料塊的偏移量，BlockDataSize表示索引指向資料塊在磁盤上的大小，BlockKey表示索引指向資料塊中的第一個key。除此之外，還有另外3個字段用來記錄MidKey的相關資訊，MidKey表示HFile所有Data Block中中間的一個Data Block，用于在對HFile進行split操作時，快速定位HFile的中間位置。需要注意的是single-level索引結構和mutil-level結構相比，就隻缺少MidKey這三個字段。
Root Index Block會在HFile解析的時候直接加載到記憶體中，此處需要注意在Trailer Block中有一個字段為dataIndexCount，就表示此處Index Entry的個數。因為Index Entry并不定長，隻有知道Entry的個數才能正确的将所有Index Entry加載到記憶體。
NonRoot Index Block
當HFile中Data Block越來越多，single-level結構的索引已經不足以支撐所有資料都加載到記憶體，需要分化為mutil-level結構。mutil-level結構中NonRoot Index Block作為中間層節點或者葉子節點存在，無論是中間節點還是葉子節點，其都擁有相同的結構，如下圖所示：
和Root Index Block相同，NonRoot Index Block中最核心的字段也是Index Entry，用于指向葉子節點塊或者資料塊。不同的是，NonRoot Index Block結構中增加了block塊的内部索引entry Offset字段，entry Offset表示index Entry在該block中的相對偏移量（相對于第一個index Entry)，用于實作block内的二分查找。所有非根節點索引塊，包括Intermediate index block和leaf index block，在其内部定位一個key的具體索引并不是通過周遊實作，而是使用二分查找算法，這樣可以更加高效快速地定位到待查找key。
HFile資料完整索引流程
了解了HFile中資料索引塊的兩種結構之後，就來看看如何使用這些索引資料塊進行資料的高效檢索。整個索引體系類似于MySQL的B+樹結構，但是又有所不同，比B+樹簡單，并沒有複雜的分裂操作。具體見下圖所示：
圖中上面三層為索引層，在資料量不大的時候隻有最上面一層，資料量大了之後開始分裂為多層，最多三層，如圖所示。最下面一層為資料層，存儲使用者的實際keyvalue資料。這個索引樹結構類似于InnoSQL的聚集索引，隻是HBase并沒有輔助索引的概念。
圖中紅線表示一次查詢的索引過程（HBase中相關類為HFileBlockIndex和HFileReaderV2），基本流程可以表示為：
1. 使用者輸入rowkey為fb，在root index block中通過二分查找定位到fb在’a’和’m’之間，是以需要通路索引’a’指向的中間節點。因為root index block常駐記憶體，是以這個過程很快。
2. 将索引’a’指向的中間節點索引塊加載到記憶體，然後通過二分查找定位到fb在index ‘d’和’h’之間，接下來通路索引’d’指向的葉子節點。
3. 同理，将索引’d’指向的中間節點索引塊加載到記憶體，一樣通過二分查找定位找到fb在index ‘f’和’g’之間，最後需要通路索引’f’指向的資料塊節點。
4. 将索引’f’指向的資料塊加載到記憶體，通過周遊的方式找到對應的keyvalue。
上述流程中因為中間節點、葉子節點和資料塊都需要加載到記憶體，是以io次數正常為3次。但是實際上HBase為block提供了緩存機制，可以将頻繁使用的block緩存在記憶體中，可以進一步加快實際讀取過程。是以，在HBase中，通常一次随機讀請求最多會産生3次io，如果資料量小（隻有一層索引），資料已經緩存到了記憶體，就不會産生io。
索引塊分裂
上文中已經提到，當資料量少、檔案小的時候，隻需要一個root index block就可以完成索引，即索引樹隻有一層。當資料不斷寫入，檔案變大之後，索引資料也會相應變大，索引結構就會由single-level變為mulit-level，期間涉及到索引塊的寫入和分裂，本節來關注一下資料寫入是如何引起索引塊分裂的。
1. append階段：memstore中keyvalue首先會寫入到HFile中資料塊
2. finalize階段：修改HFlie中meta中繼資料塊，索引資料塊以及Trailer資料塊等
append流程
具體keyvalue資料的append以及finalize過程在HFileWriterV2檔案中，其中append流程可以大體表征為：
a. 預檢查：檢查key的大小是否大于前一個key，如果大于則不符合HBase順序排列的原理，抛出異常；檢查value是否是null，如果為null也抛出異常
b. block是否寫滿：檢查目前Data Block是否已經寫滿，如果沒有寫滿就直接寫入keyvalue；否則就需要執行資料塊落盤以及索引塊修改操作；
c. 資料落盤并修改索引：如果DataBlock寫滿，首先将block塊寫入流；再生成一個leaf index entry，寫入leaf Index block；再檢查該leaf index block是否已經寫滿需要落盤，如果已經寫滿，就将該leaf index block寫入到輸出流，并且為索引樹根節點root index block新增一個索引，指向葉子節點(second-level index)
d. 生成一個新的block：重新reset輸出流，初始化startOffset為-1
e. 寫入keyvalue：将keyvalue以流的方式寫入輸出流，同時需要寫入memstoreTS；除此之外，如果該key是目前block的第一個key，需要指派給變量firstKeyInBlock
finalize階段
memstore中所有keyvalue都經過append階段輸出到HFile後，會執行一次finalize過程，主要更新HFile中meta中繼資料塊、索引資料塊以及Trailer資料塊，其中對索引資料塊的更新是我們關心的重點，此處詳細解析，上述append流程中c步驟’資料落盤并修改索引’會使得root index block不斷增多，當增大到一定程度之後就需要分裂，分裂示意圖如下圖所示：
上圖所示，分裂前索引結構為second-level結構，圖中沒有畫出Data Blocks，根節點索引指向葉子節點索引塊。finalize階段系統會對Root Index Block進行大小檢查，如果大小大于規定的大小就需要進行分裂，圖中分裂過程實際上就是将原來的Root Index Block塊分割成4塊，每塊獨立形成中間節點InterMediate Index Block，系統再重新生成一個Root Index Block（圖中紅色部分），分别指向分割形成的4個interMediate Index Block。此時索引結構就變成了third-level結構。
總結
這篇文章是HFile結構解析的第二篇文章，主要集中介紹HFile中的資料索引塊。首先分Root Index Block和NonRoot Index Block兩部分對HFile中索引塊進行了解析，緊接着基于此介紹了HBase如何使用索引對資料進行檢索，最後結合Memstore Flush的相關知識分析了keyvalue資料寫入的過程中索引塊的分裂過程。希望通過這兩篇文章的介紹，能夠對HBase中資料存儲檔案HFile有一個更加全面深入的認識。
本文轉載自：http://hbasefly.com
<a href="http://hbasefly.com/2016/04/03/hbase_hfile_index/" target="_blank">原文連結</a>