Dremel是google推出的又一神器，paper中宣稱能夠在3s內(nèi)分析1PB的數(shù)據(jù)，主要是面向交互式查詢。這篇paper對嵌套類型的存儲方式方面，思維確實(shí)有些跳躍，這篇文章主要講講這個，一方面是方便后來者理解，另一方面是讓自己也整理下思路。

    首先Dremel使用的是列存模型，對于基本類型列存較容易做到；但是對于嵌套類型，Dremel也能做到將其拆解成基本類型并進(jìn)行列存，這是值得我們研究的。

    直觀看下嵌套類型按行存儲和拆解后按列存儲的對比效果：

    然后對于嵌套數(shù)據(jù)類型，Dremel里面定義了里面三種類型的字段

    1，必須出現(xiàn)1次而且僅出現(xiàn)1次的字段：required

    2，可能出現(xiàn)1次或者0次的字段：optional

    3，可能出現(xiàn)0次或者N次字段：repeated

    下面以paper的例子來講述吧：

    其中DocId是required字段，因此在r1,r2中必須出現(xiàn)1次；url字段是optional字段，因此在r1的第三個Name里未出現(xiàn)，在r1的前兩個Name里出現(xiàn)了1次；Backward字段是repeated字段，因此在r1的Links里未出現(xiàn)，在r2的Links里出現(xiàn)了2次。

    理解了上面這些，直接來看下Dremel是怎么來存它的吧：

    上表中的每條記錄都有兩個屬性，"r"代表repetition level，"d"代表definition level，定義如下：

    repetition level:what repeated field in the field’s path the value has repeated，記錄該字段是在哪個repeated級別上重復(fù)的

    definition level:how many fields inpthat could be undefined (because they are optional or repeated) are actually present，記錄該字段之上有多少個optional或者repeated字段實(shí)際是有值的（本來可以為null的）

    看到這里，各位可能已經(jīng)在心里默念了：WTF！別急，可以結(jié)合一個例子來看：

先看repetition level（下面以r替代），以Name.Language.Code為例：

    1)對第1個出現(xiàn)的值，其r始終為0，因此'en-us'的r為0

    2)對于第2個值'en'，其上一個值是'en-us'，它們是在Language級別發(fā)生的重復(fù)，Name.Language是兩級的repeated字段，因此r為2

    3)對于第3個值null，是為了記錄'en-gb'是出現(xiàn)在第三個Name而非第二個Name里，特意占位用的。null的上一個值是'en'，它們是在Name級別發(fā)生的重復(fù)，因此r是1

    4)對于第4個值'en-gb'，其上一個值是null，它們也是在Name級別發(fā)生的重復(fù)，因此r是1

    5)對于第5個值null，其上一個值是'en-gb'，它們出現(xiàn)在兩個不同Document里，因此r是0

    總結(jié)下，看repetition level注意兩點(diǎn)：1,只比較該值和上一個值；2,只需要看這兩個值的重復(fù)位置上有幾個repeated字段

再看definition level（下面以d替代），也以Name.Language.Code為例：

    1)對于'en-us'，其上的Name，Language都出現(xiàn)了，因此d為2（其實(shí)對于非null值的字段，其上的optional或者repeated字段肯定是出現(xiàn)了，所以都是相同的，只是null字段的d值有差別）

    2)對于'en'，同理d也為2

    3)對于null，其上只出現(xiàn)了Name，沒有出現(xiàn)Language，因此d為1

    4)對于'en-gb',d也為2

    5)對于最后一個null，其上也只出現(xiàn)了Name，沒有出現(xiàn)Language，因此d為1

    以上只是講了dremel怎么去存嵌套類型，至于這種存法是怎么想出來的，真非我輩能理解的了。。。更多內(nèi)容，請參考原著paper及網(wǎng)上解析。