上篇文章從整體介紹了Orcfile的存儲(chǔ)格式，接下來重點(diǎn)介紹下Orc里用到的幾種編碼格式：
字典編碼：用于String類型的字段
Run-Length編碼：用于int，long，short等類型的編碼
Bit編碼：可以用于各種數(shù)據(jù)類型
1，字典編碼：
對(duì)于String類型的每個(gè)字段分別保存一個(gè)字典，記錄每個(gè)值在字典中的位置，保存字典的數(shù)據(jù)結(jié)構(gòu)采用一棵紅黑樹。對(duì)于每個(gè)String字段，最終會(huì)有三個(gè)輸出Stream，分別是StringOuptut(記錄字典中的值)，LengthOutput(記錄每個(gè)字典值的長度)，RowOutput(記錄字段在字典中的位置)。
思考1：為什么要用紅黑樹？
因?yàn)榧t黑樹無論是插入，刪除，查找的性能都比較平均，都是O(logN)，而且是平衡查找樹，最壞情況也不會(huì)退化成O(N)
思考2：其實(shí)一般存儲(chǔ)時(shí)還會(huì)使用LZO之類的壓縮，它們本身就是一種字典壓縮，為什么Orc里面要自己做字典壓縮？
因?yàn)長ZO之類的壓縮窗口一般比較小（LZO默認(rèn)是64KB），而Orc的字典壓縮是以整個(gè)字段為范圍來壓縮的，壓縮率會(huì)更好。
2，Run-Length編碼：
對(duì)于int,long,short類型的字段，使用Run-Length編碼。該Run-Length能夠?qū)Φ炔顢?shù)列（完全相等也屬于等差數(shù)列）進(jìn)行壓縮，該等差數(shù)列需要滿足以下兩個(gè)條件：
1，至少包含3個(gè)元素
2，差值在-128~127之間（因?yàn)椴钪涤?Byte來表示）
對(duì)于不滿足等差數(shù)列的數(shù)字，Run-Length編碼也能存儲(chǔ)，但是沒有壓縮效果，Run-Length的具體存儲(chǔ)如下：
第一個(gè)Byte是Control Byte，取值在-128~127之間，其中-1~-128代表后面存儲(chǔ)著1~128個(gè)不滿足等差數(shù)列的數(shù)字，0~127代表后面存儲(chǔ)著3~130個(gè)等差數(shù)列的數(shù)字；
如果Control Byte>=0，則后面跟著一個(gè)Byte存儲(chǔ)差值，否則不存儲(chǔ)該Byte；
如果Control Byte>=0，則后面跟著等差數(shù)列的第一個(gè)數(shù)，否則跟著-Control Byte個(gè)數(shù)字。
例子：
原始數(shù)字：12,12,12,12,12,10,7,13
經(jīng)過Run-Length的數(shù)字：2,0,12,-3,10,7,13
紅色代表Control Byte，黃色代表差值，黑色代表具體的數(shù)字。
3，Bit編碼：
對(duì)所有類型的字段都可以采用Bit編碼來表示該值是否為null。在寫任何類型字段之前，先判斷該字段值是夠?yàn)閚ull，如果為null則bit值存為0，否則存為1，對(duì)于為null的字段在實(shí)際編碼時(shí)不需要存儲(chǔ)了。經(jīng)過Bit編碼之后，可以對(duì)于8個(gè)bit組成一個(gè)Byte，再對(duì)其進(jìn)行Run-Length編碼。
其實(shí)除了這三種編碼格式之外，Orc對(duì)于hive的復(fù)雜類型array,map,list等，將其降維成基本類型來存儲(chǔ)，這個(gè)也是值得借鑒的，如果有空之后會(huì)進(jìn)行分析。