小编Ral*_*alf的帖子

作为一个简化的例子，假设我有一个这样的表：

seq | value
----+------
102 | 11954
211 | 43292
278 | 19222
499 |  3843

该表可能包含数亿条记录，我需要经常做这样的查询：

SELECT sum(value) WHERE seq > $a and seq < $b

即使seq被索引，典型的数据库实现也会遍历每一行以计算最佳情况下的总和O(n)，其中n是范围的大小。

是否有任何数据库可以像O(log(n))每个查询一样有效地执行此操作？

我所遇到的数据结构称为段树所描述这里。有时也称为范围树或区间树，尽管所有这些名称通常被描述为数据结构的略微不同的变体。

但是，我还没有遇到任何实现这种数据结构的数据库。对于内存结构来说，从头开始实现它很容易，但如果它必须持久化或太大而无法放入内存，则变得棘手。如果有一种在现有数据库之上实现这一点的有效模式，那也会有所帮助。

旁注：这不是仅附加表，因此在这种情况下，诸如保留累积总和之类的解决方案将不起作用。