上篇文章從整體介紹了Orcfile的存儲(chǔ)格式，接下來(lái)重點(diǎn)介紹下Orc里用到的幾種編碼格式：

    字典編碼：用于String類(lèi)型的字段

    Run-Length編碼：用于int，long，short等類(lèi)型的編碼

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

1，字典編碼：

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

    思考1：為什么要用紅黑樹(shù)？

    因?yàn)榧t黑樹(shù)無(wú)論是插入，刪除，查找的性能都比較平均，都是O(logN)，而且是平衡查找樹(shù)，最壞情況也不會(huì)退化成O(N)

    思考2：其實(shí)一般存儲(chǔ)時(shí)還會(huì)使用LZO之類(lèi)的壓縮，它們本身就是一種字典壓縮，為什么Orc里面要自己做字典壓縮？

    因?yàn)長(zhǎng)ZO之類(lèi)的壓縮窗口一般比較小（LZO默認(rèn)是64KB），而Orc的字典壓縮是以整個(gè)字段為范圍來(lái)壓縮的，壓縮率會(huì)更好。

2，Run-Length編碼：

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

    1，至少包含3個(gè)元素

    2，差值在-128~127之間（因?yàn)椴钪涤?Byte來(lái)表示）

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

    第一個(gè)Byte是Control Byte，取值在-128~127之間，其中-1~-128代表后面存儲(chǔ)著1~128個(gè)不滿(mǎn)足等差數(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)過(guò)Run-Length的數(shù)字：2,0,12,-3,10,7,13

    紅色代表Control Byte，黃色代表差值，黑色代表具體的數(shù)字。

3，Bit編碼：

對(duì)所有類(lèi)型的字段都可以采用Bit編碼來(lái)表示該值是否為null。在寫(xiě)任何類(lèi)型字段之前，先判斷該字段值是夠?yàn)閚ull，如果為null則bit值存為0，否則存為1，對(duì)于為null的字段在實(shí)際編碼時(shí)不需要存儲(chǔ)了。經(jīng)過(guò)Bit編碼之后，可以對(duì)于8個(gè)bit組成一個(gè)Byte，再對(duì)其進(jìn)行Run-Length編碼。

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