上篇文章從整體介紹了Orcfile的存儲格式，接下來重點介紹下Orc里用到的幾種編碼格式：

    字典編碼：用于String類型的字段

    Run-Length編碼：用于int，long，short等類型的編碼

    Bit編碼：可以用于各種數(shù)據(jù)類型

1，字典編碼：

    對于String類型的每個字段分別保存一個字典，記錄每個值在字典中的位置，保存字典的數(shù)據(jù)結(jié)構(gòu)采用一棵紅黑樹。對于每個String字段，最終會有三個輸出Stream，分別是StringOuptut(記錄字典中的值)，LengthOutput(記錄每個字典值的長度)，RowOutput(記錄字段在字典中的位置)。

    思考1：為什么要用紅黑樹？

    因為紅黑樹無論是插入，刪除，查找的性能都比較平均，都是O(logN)，而且是平衡查找樹，最壞情況也不會退化成O(N)

    思考2：其實一般存儲時還會使用LZO之類的壓縮，它們本身就是一種字典壓縮，為什么Orc里面要自己做字典壓縮？

    因為LZO之類的壓縮窗口一般比較小（LZO默認是64KB），而Orc的字典壓縮是以整個字段為范圍來壓縮的，壓縮率會更好。

2，Run-Length編碼：

    對于int,long,short類型的字段，使用Run-Length編碼。該Run-Length能夠?qū)Φ炔顢?shù)列（完全相等也屬于等差數(shù)列）進行壓縮，該等差數(shù)列需要滿足以下兩個條件：

    1，至少包含3個元素

    2，差值在-128~127之間（因為差值用1Byte來表示）

    對于不滿足等差數(shù)列的數(shù)字，Run-Length編碼也能存儲，但是沒有壓縮效果，Run-Length的具體存儲如下：

    第一個Byte是Control Byte，取值在-128~127之間，其中-1~-128代表后面存儲著1~128個不滿足等差數(shù)列的數(shù)字，0~127代表后面存儲著3~130個等差數(shù)列的數(shù)字；

    如果Control Byte>=0，則后面跟著一個Byte存儲差值，否則不存儲該Byte；

    如果Control Byte>=0，則后面跟著等差數(shù)列的第一個數(shù)，否則跟著-Control Byte個數(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編碼：

對所有類型的字段都可以采用Bit編碼來表示該值是否為null。在寫任何類型字段之前，先判斷該字段值是夠為null，如果為null則bit值存為0，否則存為1，對于為null的字段在實際編碼時不需要存儲了。經(jīng)過Bit編碼之后，可以對于8個bit組成一個Byte，再對其進行Run-Length編碼。

    其實除了這三種編碼格式之外，Orc對于hive的復(fù)雜類型array,map,list等，將其降維成基本類型來存儲，這個也是值得借鑒的，如果有空之后會進行分析。