乾学院 50 号会员
7 回帖  •  934 浏览  • 
     ...

【性能优化】3.1 [外存查找] 二分法

 
数据蒋堂(66)

【性能优化】2.7 [外存数据集] 数据更新

3.1 二分法

如果文件中存储的外存数据表中的记录对被查找键有序，只要这种文件格式可以支持较随意的分段，我们就可以实施外存二分法查找，以避免顺序遍历整个文件。

先将文件分成两段，取出第二段的第一条记录，和查找键对比，根据对比结果再决定是在前一半还是后一半继续查找，这时要把文件分成 4 段，取第 2 段或第 4 段中的第 1 条记录再继续对比，继而分成 8 段，…，最终找到目标值。

有重复值的情况会更为复杂，向后可以直接继续遍历，向前则要继续在前半部分做二分直到找到第一个出现查找值为止，要比内存情况麻烦得多。

二分法还适用于区间式的查找，即找出被查找键在某个范围内的记录。只要找到第一个起始查找值，然后一直向后遍历直到把所有的终止查找值都找出来就可以了，不需要两边找。

这个过程并不难理解，但实现起来却较为繁琐。SPL 做了封装，可以直接使用：

A

B

1

=file("data.txt")

2

for 1000

=10000.sort(rand()).to(9000).sort()

3

>A1.export@at(B2.new(A2*10000+~-1:ID,…))

4

=A1.iselect@t(123456,ID)

5

=A1.iselect@t(123456:234567,ID)

A1-B3 生成了 900 万行 ID 有序的文本文件。使用 iselect 函数即可在有序的文件中用二分法找到目标值，也支持查找值在某个区间的形式。读者可以对比使用游标遍历的速度。

集文件也可以用这个函数。

A

1

=file("data.btx"))

2

=A1.export@b(file("data.txt").cursort@t())

3

=A1.iselect@b(123456,ID)

4

=A1.iselect@b(123456:234567,ID)

组表当然也可以，不过将使用另一个函数。

A

B

1

=file("data.ctx")

=file("data.btx").cursor@b()

2

=A1.create(#ID,…)

>A2.append(B1)

3

=A1.open()

4

=A3.find(123456)

5

=A3.cursor(;ID>=123456 && ID<=234567)

用 find 找时，要求被查找键是组表的主键，即在组表中唯一。如果区间式的查找（会返回多个目标值），则直接生成游标上加条件即可，SPL 会根据键的有序性自动跳到合适的数据块读数据，而不会真地遍历。

【性能优化】3.2 [外存查找] 哈希索引
【性能优化】 前言及目录

数据蒋堂(66)