什么是嵌套數(shù)據(jù)
嵌套數(shù)據(jù)舉例如下您宪，
圖1包含一個名為Document的數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)定義芍躏，即schema邪乍，以及兩個實例，r1和r2对竣。定義數(shù)據(jù)結(jié)構(gòu)的schema有三種修飾符庇楞，如下：
●?required：表示有且僅有一個值
●?optional：表示可選，0到1個值
●?repeated：表示重復(fù)否纬，0到N個值
所謂嵌套數(shù)據(jù)記錄其實是一種樹狀結(jié)構(gòu)吕晌，圖2是數(shù)據(jù)記錄r1的樹形表示，其中葉子節(jié)點含有真正的值临燃，字段可以用完整路徑表示睛驳。圖1所示的例子Document總共有六個字段，路徑分別為：
●?DocId
●?Links.Backward
●?Links.Forward
●?Name.Language.Code
●?Name.Language.Country
●?Name.Url
記錄按列存儲主要有正向拆解和反向構(gòu)造兩個過程：
●?正向拆解：按照不同字段對記錄進(jìn)行拆解膜廊，相同字段的值集中存儲為一列
●?反向構(gòu)造：選擇任意字段子集乏沸，重新構(gòu)造為一個數(shù)據(jù)記錄
repetition levels
因為嵌套數(shù)據(jù)記錄的字段有重復(fù)，對于重復(fù)字段（repeated修飾）的多個值爪瓜，在反向構(gòu)造的時候蹬跃，需要知道這些值是來自不同的記錄，還是來自相同記錄的重復(fù)字段铆铆。最簡單的方式是引入一個“標(biāo)志位”：0表示該值來自一個新的記錄炬转，1表示相同記錄的重復(fù)字段。
然而重復(fù)字段是嵌套的算灸，所以“相同記錄的重復(fù)字段”包含多種情況扼劈，如圖1所示record1，Code(en)（表示value為en的Code字段菲驴，下同）和Code(en-gb)都是記錄r1的重復(fù)字段荐吵，它們在記錄中的位置還需進(jìn)一步加以區(qū)分。考慮到字段是用形如x.y.z…的路徑表示先煎，所以重復(fù)字段在記錄中的“位置”贼涩，可以表示為“該重復(fù)字段出現(xiàn)在路徑哪一級”。如果記錄用樹表示薯蝎，那么所謂“路徑哪一級”指的就是樹的深度（levels）遥倦。需注意，路徑中非repeated修飾的字段不參與深度計算占锯。
比如Code字段的路徑表示為Name.Language.Code袒哥，Name和Language都是重復(fù)字段，如果在記錄中第一次出現(xiàn)消略，levels為0堡称，如果在Name處重復(fù)出現(xiàn)，levels為1艺演，在Language處重復(fù)出現(xiàn)levels為2却紧。如Code(en)在Language處重復(fù)，所以levels為2胎撤；Code(en-gb)在Name出重復(fù)晓殊，所以levels為1。
又比如Forward字段路徑為Links.Forward中伤提，Links是optional的巫俺，不參與深度計算，F(xiàn)orward是repeated的飘弧，所以识藤，如果在Forward處重復(fù)出現(xiàn)，levels為1（注意：不為2）次伶。
這所謂的levels在Dremel中就是repetition levels痴昧，其定義如下：
“…? at what repeated field in the field’s path the
value has repeated.”
意思是“在路徑中的什么重復(fù)字段，此值重復(fù)了”冠王，通俗來說就是“在哪一級重復(fù)”赶撰。
逐個讀取列存儲中的repetition
levels豪娜，就能夠初步還原value在原有數(shù)據(jù)中的位置，以字段Name.Language.Code為例：
????????1）第1個value是en-us哟楷，repetition levels=0表示沒有任何重復(fù)瘤载，表明這是一個新的record的開始，也表明en-us處在第1個Name的第1個Language卖擅。
? ? ? ? 2）第2個value是en鸣奔，repetition levels=2表示en在Language重復(fù)墨技，也就是說不在Name處重復(fù)，表明和上一個值en-us處在同一個Name挎狸，即en處在第1個Name的第2個Language
????????3）第3個value是NULL扣汪，repetition levels=1表示NULL在Name處重復(fù)，表明NULL處在一個新的Name锨匆，第2個Name崭别。之所以要插入一個NULL值，為了計算出第4個value‘en-gb’出現(xiàn)在第3個Name恐锣，否則的話就會被認(rèn)為處在第2個Name
? ? ? ? 4）第4個value是en-gb茅主，repetition levels=1表示en-gb處在一個新的Name，即第3個Name
? ? ? ? 5）第5個value是NULL侥蒙，repetition levels=0表明這是一個新的記錄的開始
Definition levels
如果value不為NULL暗膜，通過repetition levels就能夠確定其所在位置匀奏。但如果value為NULL鞭衩，僅有repetition levels還無法完全確定其所在位置。
以Name.Language.Country字段為例娃善，第3個value是NULL论衍，repetition
levels=1表明當(dāng)前NULL處在第2個Name（需要結(jié)合前面兩個value的repetition
levels計算得出）。但由于Name下面有兩級定義聚磺，Language和Country坯台，Language是repeated類型的，重復(fù)次數(shù)可能為0瘫寝，即可能沒有定義蜒蕾，Country是optional可選類型，也可能沒有定義焕阿，既然都有可能沒定義咪啡，僅有NULL就無法知道是在Language這一級NULL還是在Country這一級NULL。
因此暮屡，對于optional或repeated類型字段撤摸，需要一個標(biāo)示顯示的表明NULL型value定義在哪一級，這就是Dremel中的definition levels褒纲，定義如下：
“...how many fields in path that could be undefined (because they are
optional or repeated) are actually present in the record”
即“在路徑中有多少個可選字段或重復(fù)字段實際上是有值的”准夷。
???????? 以圖3所示Name.Language.Country為例進(jìn)行說明：
●?第1個NULL value的definition levels為2，表示Name和Language有定義莺掠，Country沒有定義
●?第2個NULL value的definition levels為1衫嵌，表示Name有定義，Language就沒有定義了
進(jìn)一步看非NULL的value彻秆。Country為us和gb的value楔绞，其definition
levels為都3论悴，表示Name、Language和Country都有定義墓律。Name.Language.Code字段膀估，Code為required類型，Name和Language是repeated類型耻讽，所以Code字段的definition levels取值1或2察纯，value en-us、en针肥、en-gb等definition levels為2饼记，NULL value的defition為1。
不難發(fā)現(xiàn)慰枕，非NULL的value具则，其definition levels為路徑深度的最大值。NULL的value具帮，其definition levels都小于路徑深度最大值博肋。基于該特點蜂厅，可以不用保存NULL value盟戏，僅保存其definition levels即可匪燕。
參考
[1] Dremel論文
