type
status
date
slug
summary
tags
category
icon
password
这个算法解决的是基于列式存储，Parquet 是如何支持嵌套格式的问题。
支持复杂格式
在嵌套格式里，可能会出现 List、Map 之类的结构，Parquet 使用 required、optional、repeated 三个字段去支持这些结构。含义分别代表：
- required：有且只有一次
- optional：0 或 1 次
- repeated：0 或多次
对于 List 可以参考下面这个格式定义：
对于 Map 可以参考下面这个格式定义：
当然， List 和 Map 还可以互相嵌套。
Repetition Level
使用列式存储遇到的第一个问题是如何区分两段数组，例如对于下面这条数据：
对应的结构如下，代表 list 和 element 都是可以重复的字段：
按照列式存储的思想，我们会把 list.lower 这个字段的数据都存储在一起，即
问题来了，我们不能判断 b、c、d、e 究竟是属于前一个 list 还是后一个 list。
Parquet 使用 repetition level 来解决这个问题。
repetition level 只与 repeated 类型的字段有关，例如，起始的嵌套层级是 level 0，在上面这个例子，还有另外两层嵌套：list 是 level 1，element 是 level 2。
repetition level 记录的是嵌套层级的变化：
1）如果当前值是一个新数组的开始，repetition level 值等于重复开始的嵌套层级。
2）如果当前值不是一个新数组的开始，repetition level 值等于这个字段的嵌套层级。
上面的例子里，对应的编码如下：
list.lower | repetition level |
a | 0 |
b | 2 |
c | 1 |
d | 2 |
e | 2 |
说明如下：
1）a 是新数组的开始，但是因为没有前一个数组，它的 repetition level 是 0；
2）c 是新数组的开始，前一个数组是在 list 层重复，它的 repetition level 是 1；
3）其他字母不是新数组的开始，它们是在 element 层重复，它的 repetition level 就是 2。
如果嵌套层级不等于它实际的层级，说明开始了一个新数组。因此，这里的 a、c 截断出了两个数组。
Definition Level
只有 Repetition Levels 还存在一个问题，那就是不能处理字段为空的情况。
以下面这个情况为例：
考虑对 list.upper 字段进行按列存储,因为第一个 list 里没有保存 upper 字段，最后一条数据也没有出现 upper 字段，都用 null 代替，得到：
对应的编码如下：
list.upper | repetition level |
null | 0 |
C | 0 |
D | 2 |
E | 2 |
null | 0 |
这样，仅凭 repetition level 字段，不能知道第一个 upper 是在已经定义好的 list 里面的，而第二个 upper 则是没有 list 定义的。使用 definition level 可以表达 null 的位置。
definition level 的值等于该列的路径上标示为 optional 或者 repeated 的个数。
list.upper | definition level |
null | 1 |
C | 2 |
D | 2 |
E | 2 |
null | 0 |
说明如下：
1）第一个 null 的路径上有一个 repeated （list）, definition level = 1；
2）C、D、E的路径上有两个 repeated（list、upper）, definition level = 2；
3）第一个 null 的路径上没有 repeated, definition level = 0。
这样，通过 definition level 我们可以知道 null 值究竟代表在哪个层级上的这个字段为空。
并且，Parquet 还可以不存储这个 null 值，只要是 definition level 值小于这个列路径上的 optional + repeated 个数，那么说明这个列一定是没有定义，null 值可以不保存。
总结
在存储时根据每列的情况把 Repetition Levels 和 Definition Levels 两个字段一起加上去。在读取文件时根据 Repetition Levels 和 Definition Levels 两个字段就可以把数据还原回来了，这就是 striping and assembly 算法。
需要说明的是，为每个值都加上 repetition level 和 definition level 两个字段可能带来性能损耗，Parquet 做很多的优化措施，并且也通过特别的编码对这部分数据进行了压缩。
最后，给出这个方法提出时用的例子，大家可以根据上面的理解去分析这两个字段的值：
