有序存储是将数据按照某些字段（通常是主键或部分主键）排序后，连续写入外存（主要是硬盘）。有序存储能实现低成本的数据压缩，能够避免频繁跳跃的读取硬盘。而且，计算时从硬盘中连续读出的就是排好序的数据，能够实施专为有序设计的高性能算法，如：二分法查找、快速过滤、有序分组、有序关联等等。这里我们详细介绍 SPL 有序存储的原理。

存储结构

SPL 组表支持行存和列存两种方式，程序员要按照场景来选择。来源数据通常是分批写入组表的，每一批包含若干条记录。而行存组表也是按照记录连续存储数据的，SPL 只要将每一批源数据按记录依次写入组表文件即可。计算时，顺序读取记录就可以了。生成行存组表的代码大致是这样的：

file("T-r.ctx").create@r(#f1,#f2,f3...).append(cs)

// 建立行存组表，并将来自游标 cs 的数据写入组表。f1 和 f2 前面有 #，代表这两个字段有序。这里显式指定有序字段，便于编写计算代码时利用有序的特征。

和行存不同，列存本质上是将各个记录的相同字段存储在一起，不同字段存储在不同区域。如果计算中用到两个或以上字段，要分别找到这些字段值，组合起来再使用。生成列存组表时，SPL 先划分出一定大小的数据块，每个数据块只存储同一个字段的数据。再将每一批源数据的字段值分别写入对应字段的数据块。当某字段写满一个数据块后，要跳过已经存储了其他字段的数据块，产生新数据块，继续写入该字段的数据。这些数据块的起止位置和大小不会随着数据的追加而改变。

假设数据表共有 m 个字段 F1 到 Fm，这时候形成的列存组表大致是下面这样：

上图中，block#k 代表第 k 个数据块。一个字段在同一个数据块中是连续存储的，但这个字段占用的多个数据块却常常是不连续的。例如上图中的字段 F1 在数据块 block#1 中是连续的，但存储 F1 的下一个数据块并不是 block#2 而是 block#x。虽然 F1 的两个数据块不连续，但是只要每个数据块足够大，就可以避免硬盘的频繁随机读取。对于主流硬盘来说，数据块超过 1M 后，跳动成本占比就非常小，可以认为每一个字段都是逻辑上连续的。

将列存组表有序字段连续存储后，相邻字段值相同的可能性很大。这种情况下，SPL 只存入一个值和重复的数量，不必把同样的值存储多遍，有效的压缩了数据，可以节省大量存储空间。

生成列存组表的 SPL 是这样的：

file("T-c.ctx").create(#f1,#f2,f3...).append(cs)

// 建立列存组表，并将来自游标 cs 的数据写入组表。同样的，# 表示字段有序。代码很简单，但是封装了上述分块、列存有序压缩等算法。

SPL 组表在追加数据时并不检查字段的有序性，需要程序员自己保证写入数据确实是有序的。

数据有序存储之后，可以利用这个特征来实施高性能算法。比如常见的二分法查找。SPL 二分法查找的代码也很简单：

= file("data.ctx").open().find(123456)

// 打开组表，用二分法查找主键值为 123456 的记录。

再比如区间条件过滤。组表文件头部记录了分块的起始位置。对有序字段过滤时，可以按照起始位置直接取得记录，对比记录中有序字段的值和过滤条件，再加上有序性来判断本块中有没有查找目标，如果没有则直接跳过。这样，能减少数据读取量，节省计算时间。

= file("data.ctx").open().cursor(f1,f2,f4;f1>=123456 && f1<234567)

// 打开组表，按照有序字段 f1 做区间式查找。

少量修改

存储的数据生成之后，可能会有数据变动操作，包括插入、删除和修改。为保证高性能，组表上不能直接进行这些操作：修改的新值不一定和原值一样长，无法在原位上直接替换；组表也没有预留空白来插入数据，而删除则会造成数据的不连续。我们也可以重写组表来实现数据变动，但是，这需要重新排序以保持有序存储，再加上要重新生成组表，耗时会非常长。

对于有主键的组表，SPL 提供补区机制实现少量的数据变动。也就是在组表文件中划分出单独的补区（如下图），用于存储变动的数据。

读取这个组表时，补区的数据（黄色部分）和正常数据（蓝色部分）一起归并计算。

数据变动操作的代码大致是这样的：

补区机制可以用很短的时间完成数据变动操作，同时还可以保证读取数据的有序性。而且，补区对于 SPL 程序员来说是透明的，语法不变。

只有少量变动时，补区对性能的影响很小。但经过多次修改后，补区会越来越大，对性能的影响也会变大。因此，需要定期对补区进行清理，将其合并进原数据区，并清除补区。

下图简单描述了使用 reset@q 清理补区的方法：

假设数据按照主键升序存储。图中，SPL 先确定补区最小的主键值，再在正常数据内找到这个值，即黄色箭头位置。在这之前的正常数据（蓝色部分）不动，从黄色箭头位置开始重写组表。这样，既可以保证主键有序，又可以减少重写的数据量，节省时间。

定期追加

有些有序数据不会发生插入、删除或者修改，但是会不断有新数据追加进来，新数据不一定能在原数据最后直接追加。比如为了方便进行用户相关统计，订单组表按照用户 ID 有序存储。而新订单数据通常是以时间为序，时间比组表中数据晚，但用户 ID 还是同样的一批值，直接追加会破坏用户 ID 的顺序。如果用新旧数据一起做大排序，再重新生成组表，则耗时会非常长。

这时可以将数据组表文件分为两部分：历史数据组表 hisdata.ctx 和增量数据组表 newdata.ctx，每次追加只对增量数据组表，一段时间后，再将增量数据与历史数据归并。具体方法大致可以用下面的示意图表示：

将新数据按照历史数据组表的有序字段排序后，和增量数据组表有序归并。这样，每次只需要新数据和增量数据组表做归并排序，涉及数据量就少了很多。读取组表时，分别从两个文件中读取数据，归并后得到结果集，结果集仍然有序。这会比访问单个文件时性能下降一些，但仍然能够利用到有序。

这种方案和补区不同，即使增量数据组表随着时间逐渐变的很大，也不大影响访问性能。但太大了会导致每次追加数据时变慢，所以也需要定期合并，形成一个更大的组表，再把增量数据组表清空。比如，每天新增的数据都归并到增量数据组表中，每月 1 日合并两个组表。SPL 代码是这样的：

读数据时，需要将历史数据组表与增量数据组表归并后使用，例如：

=[file("hisdata.ctx").open().cursor(),file("newdata.ctx").open().cursor()].merge(#1)。

这里需要注意的是，游标序列中应同数据文件的先后顺序，即 [历史数据, 增量数据]。

批量删除

按照日期有序的组表，会出现大量数据过期的情况。比如：历史表 data 对日期等字段有序，存储 2010 年后 10 年的数据。到第 2014 年时，2010 年的数据过期了，需要删掉。而数据是按日期有序的，删除前面的数据会导致整个组表重写一遍，非常耗时。

SPL 提供了复组表，可以快速、便捷的删除过期数据。复组表是用多个文件构成一个组表，这些文件称为复组表的分区。用不同的分区存储不同日期段的数据，当某一个分区存储的数据过期，直接删除对应文件即可。复组表机制可以用下图来示意：

1 号分区数据过期了，直接删除文件 1。再打开组表的时候不加入 1 号分区就可以了，不需要重写其他分区中的数据。对应的代码大致是这样：

A1创建组表，设置了10个分区，每个分区有分区号1、2、…、10。year(dt)-2009是分区号表达式，是指按照年份把数据分到不同分区。使用选项 append@x 追加数据时，SPL 会针对每条追加记录计算year(dt)-2009，根据结果把数据追加到相应分区号的文件中。如果删除了1号分区，A2中打开组表的时候，只打开2到10号分区即可。

利用复组表删除过期数据，实际上是在删除文件，速度非常快。如果不用复组表，就要把剩余数据全部重写一遍。即使数据已经按日期有序，不必重新排序，但全部重写还是非常耗时。当然，也可以人为多建几个组表文件，每个装一个时间段的数据，计算时把众多文件再连起来，这就是复组表的思路。只是人为实现时代码会比较复杂，复组表将这些过程封装起来，代码更为简化。