【性能优化】1.4 [内存查找] 哈希索引

1.5 多层序号定位

前面讲过，不能针对身份证号直接使用序号定位的方法。但在某些特定情况下，还有变通的手段。

我们仍以用身份证号查找人员为例。如果待查找人群具有一些共同的特征，比如入学儿童的出生日期都会落在两三年之内，所在地区也相近。这些特征会导致身份证号的分布相对集中，而不会布满所有 18 位自然数构成的范围。利用这个特征，可以构造多层的序号定位方法以减少实施序号定位时占用的空间。

设 T 是待查找人群序表，ID 是身份证号字段。A1 将 T 的成员按其 ID 的出生年月日位分到 999999 个分组子集中，年份只要看后两位即可，不会有重复的；A2 再将每个非空的分组子集再按 ID 的前 6 位，也就是地区编号，分成 999999 个更小的分组子集；A3 进一步把 A2 的分组子集的分组子集再按 ID 的后三位（不要第 18 位校验位）分成 999 个子集。这三行代码看起来有点复杂，其实并不难理解，结果就是个三层序列。

A4 是查找值，同样解出这三部分构成的数字，也就是 A5/B5/C5，然后直接使用三层的序号定位就可以找到目标值了。三次序号定位的复杂度还是 O(1)，能跑得非常快。

这种多层方式和之前讲的序号定位有什么不同？我们以这个三层序列为例来讨论它占用的空间。

第一层中，如果这个人群的出生日期都集中在两三年内，那么，长度为 999999 的序列中，大概只有 1000 个左右是非空的，而对于空成员，就没有下一层序列了，也就是说第二层大概只有 1000 个左右的序列。第二层每个分组子集的长度也是 999999，那么总成员数大约是 1000*999999 个；同样，因为地区也都接近，这一层中每个分组子集大概也只有 1000 个是非空值，这样，第三层就也会只有 1000*1000 个左右的分组子集是非空的，第三层每个分组子集的长度是 999，总成员数大约是 1000*1000*999。这三层序列的成员数加起来也就不到 2G，占用空间也就是几个 G 或 10 几个 G，现代计算机都能装得下。而我们之前已经讨论过单层序列反而是放不下的。

总结一下：把多层序列看成一个树状结构，如果数据满足前述的分布集中的特征，那么看上去这个树会有大部分树枝延伸不到最深的层次，而在较浅的层次就中断了，也就不再占用空间。整个树占用的空间有可能很小，小到内存可以放得下的地步。

多层序号定位只能在分层后前几个层次中空值很多的情况下使用，如果空值较少甚至没有空值，多层序号结构占用的空间比单层还要更大。

除了像上面那样用多层序列实现外，SPL 还提供了处理多层序号的数据类型，称为排号键，可以支持最多 16 层序号，每层的序号范围是 0-255，也就是用两个 long 的每个字节表示一层。

A1 定义了一个能把身份证号转换成排号键的函数，可以根据已知的数据分布特征调整排号键中层次次序（这里直接按身份证号从左到右取位，不一定最适合当时的场景），A2 将表中的身份证号转成排号键再用 @s 建立索引，即构建上述的树状层次结构，然后 find 时就可以使用它高速查找了。

多层序号使用条件比较复杂，在层次较多或生成排号键的运算较复杂时，有时也并不比普通的哈希索引更有优势。

【性能优化】1.6 [内存查找] 内表索引
【性能优化】 前言及目录