(h2與hbase)面向行or面向列的存儲模型?
1. 目錄
2. 0. 示例
3.
4. 1. h2怎麼存儲pet表的記錄?
5. 1. 1 data_leaf頁格式
6. 1. 2 data_node頁格式
7.
8. 2. hbase怎麼存儲pet表的記錄?
9. 2. 1 data block格式
10. 2. 2 data block如何存下面這些記錄?
11. 2. 3 leaf索引塊的格式:
12. 2. 4 root索引塊的格式:
13. 2. 5 intermediatelevel索引塊
<a></a>
## 0. 示例
1. create table pet (
2. id int primary key,
3. name varchar(20),
4. owner varchar(20),
5. species varchar(20),
6. sex char(1)
7. );
有如下記錄:
1. id name owner species sex
2. ===============================
3. 1001 fluffy harold cat f
4. 1002 claws gwen cat m
5. 1003 buffy harold dog f
1. h2怎麼存儲pet表的記錄?h2是一個java sql database engine，使用面向行(row-oriented)的存儲模型(如果覺得拗口，就叫基于行(row-based)的存儲模型吧)。
表中繼資料與表的記錄分開，可以通過與information_schema相關的系統表來查找中繼資料，
還可以通過jdbc的java.sql.databasemetadata提供的相關api來查找。
h2内部的存儲引擎使用頁(page)來組織資料，頁的大小預設是2k，可通過參數page_size調整，
有8種不同的頁：
data_leaf
data_node
data_overflow
btree_leaf
btree_node
free_list
stream_trunk
stream_data
本文隻是說明h2怎麼按行的方式來組織資料，是以隻重點講data_leaf、data_node這兩種頁。
### 1. 1 data_leaf頁格式
1. 項 占用位元組數
2. ======================================================
3. type 1
4. checksum 2 (程式代碼中一般是先用0值占位，等寫完一頁後對此頁的資料計算校驗和再回填)
5. parentpageid 4 (就是父data_node節點的id)
6. tableid 可變int (該頁所屬的表的id)
7. columncount 可變int (該頁所屬的表有多少列)
8. entrycount 2 (該頁有多少條記錄)
9.
10. entrycount個
11. {
12. key 可變long (如果表存在主鍵，并且是byte、short、int、long類型，這個key就是主鍵的值，否則為每行生成一個唯一的數值)
13. offset 2 (該行在此頁中的相對位置)
14. }
15.
16. entrycount個
17. {
18. columnvalues 每一行記錄從對應的offset位置開始存放，不同類型的字段會使用1個byte來辨別自己的格式
19. }
20. ======================================================
data_leaf頁并不存放表名、列名、列類型這些中繼資料
對于pet表中的三行記錄放到一個data_leaf頁中會是這樣(為了友善閱讀未細化每一個位元組，實際更複雜一些):
1. 項 值
3. type 17 (page.type_data_leaf | page.flag_last(目前隻有一個頁))
4. checksum 0x75ce (校驗和計算比較複雜，也受目前pageid、pagetype、pagesize影響)
5. parentpageid 0 (就是父data_node節點的id，0說明是root節點)
6. tableid 14 (該頁所屬的表的id)
7. columncount 5 (該頁所屬的表有多少列)
8. entrycount 3 (該頁有多少條記錄)
10. {
11. 1001, 2024, 1002, 2003, 1003, 1980 (其中1001、1002、1003是key，2024、2003、1980是offset)
12. }
13. {
14. ( / key:1001 / 1001, ‘fluffy’, ‘harold’, ‘cat’, ‘f’)
15. ( / key:1002 / 1002, ‘claws’, ‘gwen’, ‘cat’, ‘m’)
16. ( / key:1003 / 1003, ‘buffy’, ‘harold’, ‘dog’, ‘f’)
17. }
18. ======================================================
### 1. 2 data_node頁格式
當某個data_leaf頁(page0)的大小超過pagesize時，會把它切掉一部分，得到一個新的data_leaf頁(page1)，
page0從切割點開始往右的keys和記錄被轉到page1中，切割點左邊的繼續留在page0，
同時生成一個新的data_node頁作為page0、page1的父節點。
data_node頁格式
項 占用位元組數
======================================================
type 1
checksum 2 (程式代碼中一般是先用0值占位，等寫完一頁後對些頁的資料計算校驗和再回填)
parentpageid 4 (就是父data_node節點的id)
tableid 可變int (該頁所屬的表的id)
rowcountstored 4
entrycount 2
entrycount個
{
childpageid 4
key 可變long
}
======================================================
hbase使用面向列(column-oriented)的存儲模型，不需要定義表的結構(schema-free),
可以随時動态添加新的列，理論上對于列的個數沒有限制，
如果列很多，可以把相關的一組列歸屬到一個列族中(column family)，充分發揮資料的聚合特性。
通過rowkey能把同一個或多個列族中的列關聯起來，
hbase的rowkey和列族的組合有點類似于傳統關系資料庫中有外鍵引用關系的兩個關聯表，
但是隻是型像神不想，hbase中兩個不同列族是平等的，沒有主從關系，隻是通過rowkey把兩者關聯起來。
hbase的data block對應h2的data_leaf，
hbase的leaf index block對應h2的data_node，
data block的格式有點複雜，如果不打算看代碼可以不用關心的
每個block有一個33位元組的頭
===========================
前8個位元組是表示block類型的magic，對應org.apache.hadoop.hbase.io.hfile.blocktype的那些枚舉常量名，
接着4個位元組表示ondiskbyteswithheader.length - header_size
接着4個位元組表示uncompressedsizewithoutheader
接着8個位元組表示prevoffset (前一個塊的offset，比如，對于第一個塊，那麼它看到的prevoffset是-1，對于第二個塊，是0)
接着1個位元組表示checksumtype code(預設是1: org.apache.hadoop.hbase.util.checksumtype.crc32)
接着4個位元組表示bytesperchecksum(預設16k，不能小于block頭長度(頭長度是33個位元組))
最後4個位元組表示ondiskdatasizewithheader
當不使用壓縮時ondiskbyteswithheader不包含checksums,
此時checksums放在ondiskchecksum中，
當使用壓縮時checksums放在ondiskbyteswithheader
checksums就是把ondiskbyteswithheader中的所有位元組以bytesperchecksum個位元組為機關求校驗和，這個校驗和用int(4位元組)表示。
注意，在求校驗和時，ondiskbyteswithheader中還沒有checksums
預設每個data block的大小是64k(頭(33位元組)不包含在内)(可以通過hcolumndescriptor.setblocksize設定)，
64k隻是一個閥值，實際的塊大小要比它大(取決于最後存入的keyvalue的大小)，
比如上次存入的keyvalue導緻塊大小變成63k了，但是還沒到64k，那麼接着存入下一個keyvalue，如果此keyvalue有5k，
那麼這個塊的大小就變成了63+5=68k了。
=================================================================================
從這開始是重點:
data block的核心是一串keyvalue，
keyvalue的格式如下:
名稱 位元組數 說明
——————————————————————–
keylength 4 表示key所占的總位元組數
valuelength 4 表示value所占的總位元組數
rowkeylength 2 表示rowkey所占的位元組數
rowkey rowkeylength rowkey
columnfamilylength 1 表示列族名稱所占的位元組數
columnfamily columnfamilylength 列族名稱
columnname columnnamelength 列名
timestamp 8 時間戳
type 1 key類型，比如是新增(put)，還是删除(delete)
value valuelength 列值
表2.1
關于keyvalue更完整更詳細的内容請看這裡:
id name owner species sex
===============================
1001 fluffy harold cat f
1002 claws gwen cat m
1003 buffy harold dog f
把id作為rowkey，其他列不動，另外hbase至少需要一個列族，假設列族名是”mycf”，這三行記錄會産生4*3=12個keyvalue，
存到data block會是這樣，先按rowkey升序，rowkey相同的按列名升序排，
最後的布局類似這樣(為了簡化去掉了一些細節):
<rowkey 列族名稱 列名 時間戳, 列值>
====================================================
<1001 mycf name timestamp, fluffy>
<1001 mycf owner timestamp, harold>
<1001 mycf sex timestamp, f>
<1001 mycf species timestamp, cat>
<1002 mycf name timestamp, claws>
<1002 mycf owner timestamp, gwen>
<1002 mycf sex timestamp, m>
<1002 mycf species timestamp, cat>
<1003 mycf name timestamp, buffy>
<1003 mycf owner timestamp, harold>
<1003 mycf sex timestamp, f>
<1003 mycf species timestamp, dog>
====================================================
與h2的data_leaf相比，
( / key:1001 / 1001, ‘fluffy’, ‘harold’, ‘cat’, ‘f’)
( / key:1002 / 1002, ‘claws’, ‘gwen’, ‘cat’, ‘m’)
( / key:1003 / 1003, ‘buffy’, ‘harold’, ‘dog’, ‘f’)
hbase的格式存在大量的備援(比如rowkey、列族名稱、列名、時間戳)之是以要這樣做是為了水準擴充、檔案合并切分更容易，
因為hbase把列名、列族名稱這些中繼資料和列值合在一起了，是以在分區時隻須簡單按rowkey切分，
就能把所有資料都轉移到另一台機器上，不需要像h2那樣要考慮information_schema中的中繼資料與表記錄是否同步的問題。
hbase基于lsm-tree來存放keyvalue，h2基于類b+tree的結構，
lsm-tree隻允許一次性添加，不需要考慮結點的删除修改，
資料會先寫到記憶體(memstore)，然後記憶體滿了就flush到硬碟變成一棵小lsm-tree，
多棵lsm-tree會定期合并成一棵更大的lsm-tree，大到一定程度再切分自動擴散到其他機器。
b+tree對于行、列的添加、删除需要對結點進行調整，資料更新會出現overflow。
另外，觀察上面兩組資料，h2的方案隻是把中繼資料抽出來放到别處了，然後通過表id把data_leaf和中繼資料關聯，
hbase 0.94可以使用字首壓縮的辦法，把重複的東西提取出來，
如果把上面的兩組資料分别串成一行，其實差别不大，隻是hbase多了很多備援資訊而已，
把備援資訊清除一部份我看不出row-oriented和column-oriented有什麼本質差別，至少hbase與h2是有點相似的。
反而差異最大的是:
1) lsm-tree與b+tree
2) 是否是schema-free的
(以下内容不重要)
資料塊總個數n(int類型,4位元組)
n個”資料塊在此索引塊中的相對位置”(從0開始，根據每個entry的大小累加，每個相對位置是int類型,4位元組)
n個entry的總位元組數(int類型,4位元組)
n個entry {
資料塊在檔案中的相對位置(long類型,8位元組)
資料塊的總長度(包括頭) (int類型,4位元組)
資料塊第一個keyvalue中的key位元組數組
n個leaf索引塊entry {
leaf索引塊在檔案中的相對位置(long類型,8位元組)
leaf索引塊的總長度(包括頭) (int類型,4位元組)
leaf索引塊第一個entry的key位元組數組
與leaf索引塊類似，隻不過它的entry在第一層intermediatelevel是leaf索引塊entry，
第二層以後是 intermediatelevel塊的entry。
查找key的順序
root索引塊 ==> intermediatelevel索引塊 ==> leaf索引塊 ==> 資料塊
本文來源于"阿裡中間件團隊播客",原文發表時間" 2012-07-31"
![DB2表壓縮功能[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)