什么是嵌套数据
嵌套数据举例如下，
图1包含一个名为Document的数据结构的结构定义，即schema，以及两个实例，r1和r2。定义数据结构的schema有三种修饰符，如下：
● required：表示有且仅有一个值
● optional：表示可选，0到1个值
● repeated：表示重复，0到N个值
所谓嵌套数据记录其实是一种树状结构，图2是数据记录r1的树形表示，其中叶子节点含有真正的值，字段可以用完整路径表示。图1所示的例子Document总共有六个字段，路径分别为：
● DocId
● Links.Backward
● Links.Forward
● Name.Language.Code
● Name.Language.Country
● Name.Url
记录按列存储主要有正向拆解和反向构造两个过程：
● 正向拆解：按照不同字段对记录进行拆解，相同字段的值集中存储为一列
● 反向构造：选择任意字段子集，重新构造为一个数据记录
repetition levels
因为嵌套数据记录的字段有重复，对于重复字段（repeated修饰）的多个值，在反向构造的时候，需要知道这些值是来自不同的记录，还是来自相同记录的重复字段。最简单的方式是引入一个“标志位”：0表示该值来自一个新的记录，1表示相同记录的重复字段。
然而重复字段是嵌套的，所以“相同记录的重复字段”包含多种情况，如图1所示record1，Code(en)（表示value为en的Code字段，下同）和Code(en-gb)都是记录r1的重复字段，它们在记录中的位置还需进一步加以区分。考虑到字段是用形如x.y.z…的路径表示，所以重复字段在记录中的“位置”，可以表示为“该重复字段出现在路径哪一级”。如果记录用树表示，那么所谓“路径哪一级”指的就是树的深度（levels）。需注意，路径中非repeated修饰的字段不参与深度计算。
比如Code字段的路径表示为Name.Language.Code，Name和Language都是重复字段，如果在记录中第一次出现，levels为0，如果在Name处重复出现，levels为1，在Language处重复出现levels为2。如Code(en)在Language处重复，所以levels为2；Code(en-gb)在Name出重复，所以levels为1。
又比如Forward字段路径为Links.Forward中，Links是optional的，不参与深度计算，Forward是repeated的，所以，如果在Forward处重复出现，levels为1（注意：不为2）。
这所谓的levels在Dremel中就是repetition levels，其定义如下：
“… at what repeated field in the field’s path the
value has repeated.”
意思是“在路径中的什么重复字段，此值重复了”，通俗来说就是“在哪一级重复”。
逐个读取列存储中的repetition
levels，就能够初步还原value在原有数据中的位置，以字段Name.Language.Code为例：
1）第1个value是en-us，repetition levels=0表示没有任何重复，表明这是一个新的record的开始，也表明en-us处在第1个Name的第1个Language。
2）第2个value是en，repetition levels=2表示en在Language重复，也就是说不在Name处重复，表明和上一个值en-us处在同一个Name，即en处在第1个Name的第2个Language
3）第3个value是NULL，repetition levels=1表示NULL在Name处重复，表明NULL处在一个新的Name，第2个Name。之所以要插入一个NULL值，为了计算出第4个value‘en-gb’出现在第3个Name，否则的话就会被认为处在第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表明当前NULL处在第2个Name（需要结合前面两个value的repetition
levels计算得出）。但由于Name下面有两级定义，Language和Country，Language是repeated类型的，重复次数可能为0，即可能没有定义，Country是optional可选类型，也可能没有定义，既然都有可能没定义，仅有NULL就无法知道是在Language这一级NULL还是在Country这一级NULL。
因此，对于optional或repeated类型字段，需要一个标示显示的表明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”
即“在路径中有多少个可选字段或重复字段实际上是有值的”。
以图3所示Name.Language.Country为例进行说明：
● 第1个NULL value的definition levels为2，表示Name和Language有定义，Country没有定义
● 第2个NULL value的definition levels为1，表示Name有定义，Language就没有定义了
进一步看非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。
不难发现，非NULL的value，其definition levels为路径深度的最大值。NULL的value，其definition levels都小于路径深度最大值。基于该特点，可以不用保存NULL value，仅保存其definition levels即可。
参考
[1] Dremel论文
