JSON中的树状结构数据简介

树状结构数据类型已经被广泛应用。社交网络数据服务推特等输出的数据类型就是JSON。Web 2.0 RESTFUL架构中推荐的数据交换格式也是JSON。许多提供公共数据下载的网站都可以使用JSON来下载数据。 Apache Hadoop、HBase等开源大数据系统中分布式通信协议采用了Protocol Buffers来实现。此外，许多物联网单片机芯片（Arduino， DragonBoard，Beagle Bone）都支持JSON格式的数据输出。大量的原始数据是树状结构数据类型。

树状结构数据类型与XML相比，具有不同的特点。XML也可以表达丰富的嵌套、多值结构，但是XML的表达引入了许多成本（例如文档类型定义（DTD）和标签）。JSON等树状结构数据类型更加简洁轻量，因此在实践中已经逐渐取代XML，成为了事实上的标准。此外，单个XML文档常常包含很多数据，具有复杂的结构，许多XML的相关研究工作正是专注于单个XML文档的处理。与此不同的是，单个树状结构数据记录相对简单，而一个数据集常常包涵大量的记录，因此研究的关注点是对大量小记录的处理。

现有的树状结构数据处理系统主要有下述三种：

1. 扩展关系型数据库系统。主流的关系数据库系统Oracle、Microsoft SQL Server、 IBM DB2和开源数据库系统PostgreSQL等都扩展了对JSON的支持。基本思路是将整个JSON记录以文本或二进制格式存放在关系表的单个属性中，提供内置函数支持JSON的解析和访问，从而可以在SQL语句中动态地解析JSON记录、提取JSON属性值，并用于SQL查询。这也是SQL/JSON工作组的基本解决方案。但是，经研究发现这种解决方案对数据分析的支持较差。数据分析操作通常只关心JSON记录的少量属性，存储和读取整条JSON记录会导致大量不必要的I/O访问。而且，每次执行SQL查询语句，都要动态地解析JSON记录，将引入很大的性能开销。

2. 行式树状结构数据处理系统。以MongoDB为代表的文档存储系统（Document Store）支持JSON的行式存储和处理。MongoDB是C/C++实现的，采用二进制的BSON格式存储JSON记录。对于JSON的属性名，BSON仍然存储其字符串；而对于JSON的原子属性值，BSON采用二进制存储。MongoDB提供一组JavaScript编程界面，可以执行与SQL查询功能相当的操作。和第一种系统相似，因为采用行式存储，数据分析操作会导致大量的I/O访问。此外，在访问JSON嵌套结构时，MongoDB需要在每个嵌套层次进行字符串比较，搜索对应的属性名，有较大的性能代价。

3. 列式树状结构数据处理系统。谷歌的Dremel提出了Protocol Buffers数据的列式存储编码方式。Apache Parquet是Dremel的开源实现，支持Parquet格式的文件存取和访问。与 Apache Hive相结合，就可以将数据存放在Parquet列式文件中，并利用Hive实现基于MapReduce的SQL查询，对大规模的树状数据进行分析。由于采用了列式存储，Parquet可以有效地避免读取不相关属性的I/O操作。但其基于MapReduce和Java的实现影响了查询的效率。

上述三种系统都采用完全通用的设计，为了支持树状结构数据类型可能出现的丰富复杂的嵌套和多值结构，引入了复杂的算法。例如，为了把多个分别存储的数据列组装还原成原始记录，Dremel的组装算法要建立一个有限状态自动机，根据自动机和列式文件中的特殊编码完成组装。除了上述讨论的每种系统各自的性能问题，这种完全通用的解决方案本身也存在相对高昂的代价。