Dremel是google推出的又一神器，paper中宣稱能夠在3s內(nèi)分析1PB的數(shù)據(jù)，主要是面向交互式查詢。這篇paper對(duì)嵌套類型的存儲(chǔ)方式方面，思維確實(shí)有些跳躍，這篇文章主要講講這個(gè)，一方面是方便后來者理解，另一方面是讓自己也整理下思路。
首先Dremel使用的是列存模型，對(duì)于基本類型列存較容易做到；但是對(duì)于嵌套類型，Dremel也能做到將其拆解成基本類型并進(jìn)行列存，這是值得我們研究的。
直觀看下嵌套類型按行存儲(chǔ)和拆解后按列存儲(chǔ)的對(duì)比效果：
然后對(duì)于嵌套數(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的第三個(gè)Name里未出現(xiàn)，在r1的前兩個(gè)Name里出現(xiàn)了1次；Backward字段是repeated字段，因此在r1的Links里未出現(xiàn)，在r2的Links里出現(xiàn)了2次。
理解了上面這些，直接來看下Dremel是怎么來存它的吧：
上表中的每條記錄都有兩個(gè)屬性，"r"代表repetition level，"d"代表definition level，定義如下：
repetition level:what repeated field in the field’s path the value has repeated，記錄該字段是在哪個(gè)repeated級(jí)別上重復(fù)的
definition level:how many fields inpthat could be undefined (because they are optional or repeated) are actually present，記錄該字段之上有多少個(gè)optional或者repeated字段實(shí)際是有值的（本來可以為null的）
看到這里，各位可能已經(jīng)在心里默念了：WTF！別急，可以結(jié)合一個(gè)例子來看：
先看repetition level（下面以r替代），以Name.Language.Code為例：
1)對(duì)第1個(gè)出現(xiàn)的值，其r始終為0，因此'en-us'的r為0
2)對(duì)于第2個(gè)值'en'，其上一個(gè)值是'en-us'，它們是在Language級(jí)別發(fā)生的重復(fù)，Name.Language是兩級(jí)的repeated字段，因此r為2
3)對(duì)于第3個(gè)值null，是為了記錄'en-gb'是出現(xiàn)在第三個(gè)Name而非第二個(gè)Name里，特意占位用的。null的上一個(gè)值是'en'，它們是在Name級(jí)別發(fā)生的重復(fù)，因此r是1
4)對(duì)于第4個(gè)值'en-gb'，其上一個(gè)值是null，它們也是在Name級(jí)別發(fā)生的重復(fù)，因此r是1
5)對(duì)于第5個(gè)值null，其上一個(gè)值是'en-gb'，它們出現(xiàn)在兩個(gè)不同Document里，因此r是0
總結(jié)下，看repetition level注意兩點(diǎn)：1,只比較該值和上一個(gè)值；2,只需要看這兩個(gè)值的重復(fù)位置上有幾個(gè)repeated字段
再看definition level（下面以d替代），也以Name.Language.Code為例：
1)對(duì)于'en-us'，其上的Name，Language都出現(xiàn)了，因此d為2（其實(shí)對(duì)于非null值的字段，其上的optional或者repeated字段肯定是出現(xiàn)了，所以都是相同的，只是null字段的d值有差別）
2)對(duì)于'en'，同理d也為2
3)對(duì)于null，其上只出現(xiàn)了Name，沒有出現(xiàn)Language，因此d為1
4)對(duì)于'en-gb',d也為2
5)對(duì)于最后一個(gè)null，其上也只出現(xiàn)了Name，沒有出現(xiàn)Language，因此d為1
以上只是講了dremel怎么去存嵌套類型，至于這種存法是怎么想出來的，真非我輩能理解的了。。。更多內(nèi)容，請(qǐng)參考原著paper及網(wǎng)上解析。