Dynamic Patricia Trie 表格

• OPS 表示每秒插入或搜索多少个 Key（1 M op/sec 表示每秒 100万 次操作）
• 吞吐率表示每秒插入或搜索的 Key 的总长度
• 顺序插入 或 顺序搜索 表示按照 Key 的 Bytewise 顺序从小到大执行插入或搜索
• 倍率 指 rbtree 或 sort 的性能是 Patricia Trie 的百分之多少
• 顺序 LB 和 随机 LB 中的 LB 指 lower_bound

作为对比，我们加入了 sort 的对比，相当于对一个 StringVector 的操作

• StringVector 进行了深度优化：
  • 使用一块连续内存保存所有的 StringData
  • 另外一块连续内存是索引，指向 StringData 中的偏移和相应 String 的长度
• sort 列的插入指在 StringVector 上逐个 Append String，然后进行排序
  • Append 开始前预分配大小刚够容纳所有 String 的内存
• sort 列的搜索指在 StringVector 上使用 std::lower_bound 语义执行搜索

FileList 作为 测试数据	avglen = 76.362     lines = 1,307,768     size = 101,171,201
	RbTree			sort			PatriciaTrie
	OPS M/s	吞吐率 MB/s	倍率 %	OPS M/sec	吞吐率 MB/s	倍率 %	OPS M/sec	吞吐率 MB/s
内存占用	194.023 MB		483.45%	110.326 MB		274.90%	40.133 MB
顺序插入	1.808	138.06	57.96%	2.423	185.06	77.69%	2.574	238.22
随机插入	0.632	48.25	38.32%	1.267	96.75	76.84%	1.649	125.91
顺序点查	2.943	224.70	51.08%	2.527	192.94	43.85%	5.761	439.93
随机点查	0.626	47.82	33.90%	1.251	95.55	36.91%	1.769	135.11
顺序 LB	2.943	224.70	51.08%	2.527	192.94	43.85%	5.761	439.93
随机 LB	0.626	47.82	33.90%	1.251	95.55	36.91%	1.769	135.11

RandKey 作为 测试数据	avglen = 5.982     lines = 865,910     size = 6,045,903
	RbTree			sort			PatriciaTrie
	OPS M/s	吞吐率 MB/s	倍率 %	OPS M/sec	吞吐率 MB/s	倍率 %	OPS M/sec	吞吐率 MB/s
内存占用	67.526 MB		334.90%	12.973 MB		53.04%	24.457 MB
顺序插入	2.36	14.10	42.11%	6.89	41.24	123.17%	5.60	33.49
随机插入	1.29	7.74	31.00%	3.49	20.89	83.73%	4.17	24.95
顺序点查	5.43	32.46	21.23%	6.42	38.38	25.09%	25.57	152.94
随机点查	1.27	7.60	10.53%	2.14	12.79	17.72%	12.07	72.20
顺序 LB	5.72	34.24	34.02%	6.69	40.00	39.75%	16.82	100.64
随机 LB	1.30	7.76	14.10%	2.153	12.88	23.39%	9.21	55.06

• shuf 列的顺序插入指生成 vector<size_t>，shuf 列的随机插入指按照 shuf 序填充 StringVector：从源中随机取，往目标中顺序填

1. 插入性能大约是 rbtree 的 200%
2. 精确搜索的性能至少要达到 rbtree 的 300%
3. 范围搜索 (lower_bound) 至少要与 rbtree 持平
4. 最坏情况下的内存占用不能超过 rbtree