快速编译以测试两个键/值数据类型对，例如（无符号整数/无符号整数）和（无符号整数/浮点数）

cargo build --release --no-default-features --features u32_u32,u32_f32 --bin qbst

完整编译（可能需要10分钟！）

cargo install --all-features --path .

示例

生成数据（已弃用）

bash脚本mkseq.bash用于生成从0开始的简单值序列

#!/bin/bash

declare -rx END=$1

echo "val"

COUNTER=0
until [ $COUNTER -ge ${END} ]; do
  echo $COUNTER
  let COUNTER+=1
done

注意：可以使用shuf命令（首先删除然后添加val）来打乱输入行。

生成数据

genfile工具生成简单的文件以测试BSTree代码。示例

genfile 10000000000 randf64 | mkbst -h test.10b.randf64 --id-type u5 --val-type f4

在包含值在[0.0, 1.0)的10亿个单精度浮点数上构建一个二叉搜索树。

生成一个包含id和值列的简单顺序文件

genfile -o 10000000000 out.csv seqint

备注

• 标识符和值使用相同的顺序号是为了测试值是否与正确的标识符关联。
• 可以使用shuf命令（先移除再添加val）来打乱输入行。

创建一个树

创建一个包含20亿个条目的简单树，条目由相同的标识符（行号）和值（行号）组成

./mkseq.bash 2000000000 | ./mkbst -h bigtest --id-type u4 --val-type u4

标识符和值都存储在常规32位无符号整数中。

执行查询

执行查询

time qbst bigtest.bstree get --value 256984
time qbst bigtest.bstree knn --value 69853145 -k 10
time qbst bigtest.bstree range --limit 10000 --from 25639 --to 250000
time qbst bigtest.bstree range --cout --from 25639 --to 250000

对1000万个随机f32值进行测试

生成1000万个随机f64，并创建一个bstree，使用32位整数存储id和32位浮点数存储值

genfile 10000000 randf64 | mkbst -h  test_10m --id-type u4 --val-type f4

查找距离0.5最近的值

time qbst test_10m.bstree nn value 0.5

查找距离0.2的10个最近值（结果按距离0.2排序）

time qbst test_10m.bstree knn -v 0.2 -k 10

计算具有值在0.4和0.6的条目数量

time qbst test_10m.bstree range -f 0.4 -t 0.6 -c

打印值在0.49999和0.50001范围内的值（结果按递增的值排序）

time qbst test_10m.bstree range -f 0.49999 -t 0.50001

基准测试

在我的个人台式机（MVNe SSD，16 GB RAM，AMD Ryzen）上测试一个包含顺序数字的20 GB文件（从0到1999999999）。

> time mkbst -h --input test.2billion.csv test2b --id-type u4 --val-type u4

real	9m49,775s
user	7m37,361s
sys	0m50,522s

构建15 GB输出文件不到10分钟（好吧，输入文件已经排序）。

> qbst test2b.bstree info

{
  "types": [
    "U32",
    "U32"
  ],
  "constants": {
    "n_entries": 2000000000,
    "entry_byte_size": 8,
    "n_entries_per_l1page": 4096,
    "n_l1page_per_ldpage": 255
  },
  "layout": {
    "depth": 2,
    "n_entries_root": 1914,
    "n_entries_main": 1999622790,
    "rigthmost_subtree": {
      "depth": 1,
      "n_entries_root": 92,
      "n_entries_main": 376924,
      "rigthmost_subtree": {
        "depth": 0,
        "n_entries_root": 286,
        "n_entries_main": 286,
        "rigthmost_subtree": null
      }
    }
  }
}

简单精确值查询

> time qbst test2b.bstree get value 1569874529

id,val
1569874529,1569874529

real	0m0,002s
user	0m0,000s
sys	0m0,002s

最近邻查询

> time qbst test2b.bstree nn -v 3000000000

distance,id,val
1000000001,1999999999,1999999999

real	0m0,002s (0m0,009s at the first execution)
user	0m0,002s
sys	0m0,000s

K最近邻查询

> time qbst test2b.bstree knn -v 25684 -k 10

distance,id,val
0,25684,25684
1,25685,25685
1,25683,25683
2,25686,25686
2,25682,25682
3,25681,25681
3,25687,25687
4,25688,25688
4,25680,25680
5,25679,25679

real	0m0,002s (0m0,005s at the first execution)
user	0m0,002s
sys	0m0,000s

范围查询

> time qbst test2b.bstree range -l 10 -f 25698470 -t 25698570

id,val
25698470,25698470
25698471,25698471
25698472,25698472
25698473,25698473
25698474,25698474
25698475,25698475
25698476,25698476
25698477,25698477
25698478,25698478
25698479,25698479

real	0m0,002s
user	0m0,000s
sys	0m0,002s

第一次执行时，限制因素是磁盘访问。第二次执行时，限制因素是操作系统处理过程所需的时间。2ms包括读取树元数据所需的时间。

生成0-20亿之间的10万个随机点

./genfile 2000000000 randint | head -100001 | tail -n +2 > toto.list

在发布模式（第三次执行）

time qbst test2b.bstree get list toto.list > toto.res.txt

real	0m0,732s
user	0m0,245s
sys	0m0,481s

即每次查询的平均时间小于8微秒！（第一次执行的平均时间约为0.14 ms/query）

> time qbst test2b.bstree nn list toto.list > toto.res.txt

real	0m16,224s
user	0m0,482s
sys	0m3,222s

> time qbst test2b.bstree nn list toto.list > toto.res.txt

real	0m1,651s
user	0m0,256s
sys	0m0,804s

> time qbst test2b.bstree nn list toto.list > toto.res.txt

real	0m0,760s
user	0m0,251s
sys	0m0,509s

• 第一次执行：0.16 ms/query
• 第三次执行：7.60 us/query

我们重新执行这些查询，对随机数进行排序

./genfile 2000000000 randint | head -100001 | tail -n +2 | sort -n > toto.list

结果相似。

我们回忆索引文件大小为15 GB，因此第二次执行更快，因为数据在磁盘缓存中。

在[0, 1)的10亿个f32随机值上进行基准测试

一次性生成值和索引

nohup sh -c "genfile 10000000000 randf64 | mkbst -h test.10b.randf64 --id-type u5 --val-type f4" &

或者分两步进行

genfile 10000000000 randf64 > test_10b_randf64.csv
mkbst -h --input test_10b_randf64.csv test.10b.randf64 --id-type u5 --val-type f4

索引的大小约为~85 GB。

查询已在两种不同的硬件上测试

• 台式计算机
  • 1 TB，7200 RPM，32 MB缓存HDD（HGST HTS721010A9E630）
  • Intel(R) Core(TM) i5-6600 CPU @ 3.30GHz（6 MB "智能缓存"）
  • 16 GB DDR4 2133 MHz
• 服务器
  • 5个SSD的RAID（三星SATA SSD）
  • 2x Intel(R) Xeon(R) CPU E5-2650 v3 @ 2.30GHz（25 MB "智能缓存"）
  • 64 GB DDR4 2133 MHz

该表返回由"time"命令提供的"真实"时间。
每个命令以time qbst test.10b.bstree加上Query params开始。

这里是在查询中使用list生成列表输入文件的命令

genfile 10000 randf64 | egrep -v "val" | sort -n > randf64_4q.csv

在最后一种情况（100000个查询，没有在磁盘缓存中）下，平均查询时间约为0.24毫秒（这可能与磁盘访问时间相差不远）。

在之前的结果中，我们清楚地看到了第一次执行时旋转磁盘与SSD磁盘的对比效果。在查询range -f 0.4 -t 0.5 -c中，我们看到服务器CPU较慢。

查询get list 10000.csv非常有意思（性能提高了超过x20！）

• 旋转磁盘的平均时间约为10毫秒
• SSD磁盘的平均时间约为0.4毫秒

对于查询get list 100000.csv > res.csv，结果时间与输入是否排序大致相同。

使用Gaia DR2数据（16亿条记录）进行基准测试

使用此BSTree索引

用例很简单：从Gaia DR2 Source的唯一标识符，我想检索相关位置（我使用格式化的位置%015.9%+015.9f作为由30个ASCII字符组成的字符串）。
因此，这里我想索引的值是Source，相关标识符是位置（是的，它与HashMap不同，在HashMap中Source将是（唯一的）键，位置是相关值，因为在BSTree中索引的值不一定是唯一的）。

输入文件看起来像

ra,dec,source
45.00431616421,0.02104503269,34361129088
44.99615368416,0.00561580621,4295806720
45.00497424498,0.01987700037,38655544960
44.96389532530,0.04359518482,343597448960
...

包含169,291,913,6行（包括标题行）。

我构建并执行以下脚本

#!/bin/bash

LC_NUMERIC=C LC_COLLATE=C; \
tail -n +2 gaia_dr2.idradec.csv | tr ',' ' ' |\
while read line; do printf "%015.11f%+015.11f,%d\n" $line; done |\
mkbst gaia_dr2_source --val 1 --id 0 --id-type t30 --val-type u8 

（由于bash的while和printf，这个过程相当慢）。

然后我有一个2.5GB的文件Gaia_source.txt，包含132,739,322个以上的Source，看起来像

2448780173659609728
2448781208748235648
2448689605685695488
2448689777484387072
2448783991887042176
...

两次连续执行（慢速7200 RPM HDD）给出

time qbst ../gaia_dr2_source.bstree get list Gaia_source.txt > Gaia.test.csv

real	24m4,323s
user	5m8,834s
sys	4m52,898s

和

time qbst ../gaia_dr2_source.bstree get list Gaia_source.txt > Gaia.test.csv

real	13m58,572s
user	4m2,162s
sys	3m32,534s

我认为第二次执行受益于HDD缓存。

现在对输入进行排序并再次查询，结果为

time qbst ../gaia_dr2_source.bstree get list Gaia_source.sorted.txt > Gaia.test.sorted.csv

real	5m53,569s
user	2m43,339s
sys	2m28,872s

输出文件大小为6.3GB。

使用PSQL10

我通过apt在Ubuntu上安装PSQL10，创建用户并将数据库移出系统盘

sudo apt-get install postgresql-10
sudo -u postgres createuser --interactive
sudo -u postgres createdb fxtests
sudo systemctrl stop postgresql
sudo rsync -av /var/lib/postgresql /data-local/psql/ 
sudo vim /etc/postgresql/10/main/postgresql.conf
sudo systemctrl start postgresql

我创建了两个表（索引表和数据表）并复制数据

CREATE TABLE gaia2_idpos (
  source BIGINT PRIMARY KEY,
  pos CHAR(30) NOT NULL
);

COPY gaia2_idpos(pos, source)
FROM '/data-local/org/gaia_dr2.idradec.4index.csv'
DELIMITER ',';

和

CREATE TABLE gaia2_id (
  source BIGINT PRIMARY KEY
)

COPY gaia2_id(source)
FROM '/data-local/org/aas/Gaia_source.txt'
DELIMITER ','

并执行查询

time psql -d fxtests -t -A -F"," -c "SELECT b.* FROM gaia2_id as a NATURAL JOIN gaia2_idpos as b" > output.csv

real	53m17,051s
user	1m4,109s
sys	0m50,723s

备注

• 我测试了未修改任何参数的PSQL
• 在PSQL测试中，使用两个表的主键，结果需要与BSTree测试中排序后的输入进行比较。

待办事项列表

• 增加通过目标列表进行查询的可能性
• 用PSQL做一个简单的测试
• 将内存映射替换为pread/pwrite？（例如，请参见positioned-io或scroll）
• 删除现在已过时的代码（例如，get被get exact visitor覆盖）
• 添加更多测试
• 添加基准测试
• 添加持续集成
• 尝试减少代码冗余（特别是在SubTreeW和SubTreeR中）
• 添加对NULL值的支持（将它们分别存储，不在树结构中）
  • 同时，我们可以使用预定义的值编码null
• 使用SQLx和PostgreSQL进行测试，以获得参考时间（如果至少一样快就很好）

致谢

如果您使用此代码并在科学公共领域（特别是天文学）工作，请承认其使用并感谢开发它的CDS。这可能有助于我们向我们的资助者推广我们的工作。

警告

如果编译失败并显示类似消息

Caused by:
  process didn't exit successfully: `rustc --crate-name bstree_file [...]
  (signal: 9, SIGKILL: kill)

，尝试

dmesg | egrep -i 'killed process'

如果结果看起来像

[...] Out of memory: Killed process xxxxx (rustc)

这意味着您的机器内存不足。

许可协议

像大多数Rust项目一样，本项目可根据您的选择使用以下任一许可协议：

• Apache License，版本2.0，(LICENSE-APACHE或http://www.apache.org/licenses/LICENSE-2.0)
• MIT许可协议(LICENSE-MIT或http://opensource.org/licenses/MIT)

任选其一。

贡献

除非您明确声明，否则您提交给本项目以供包含的任何有意贡献，根据Apache-2.0许可协议定义，应按上述方式双重许可，不附加任何其他条款或条件。