sql - 任何 DBMS 上的对数时间计数 (*) 范围查询

Question

假设有一个表 T，列 C 由 B 树索引，并且有一个给定的常量 k。假设以下查询的结果为 n:

select count(*) from T where C > k;

我在 MySQL(InnoDB) 中尝试过这样的查询，C 列由 B 树索引，发现 n 的值越大，查询越慢。在一张大 table (GB) 上，我什至不得不等待几分钟。所以，我推测时间复杂度与 n 成线性关系。但我知道是否可以在 B 树内部节点上存储聚合信息，这些信息可以在相对于表大小的对数时间内完成。

谁能推荐任何实现了对数解决方案的 DBMS，或者任何减少 MySQL 查询时间的技巧？

Answer 1

在看到执行计划之前，您什么也说不出来。至少在 Oracle 中，您还应该在 C 列上有直方图，以便为不同的 C 值制定不同的执行计划。

此外，索引的深度通常为 3-5。对数的底非常大。还要记住，许多数据库在从表中删除行时会作弊，通常叶节点可能指向已删除的行。在 B 树中维护聚合值是不值得的，它不会很好地扩展。

如果您正在寻找具有各种奇特索引选项的数据库，请查看 PostreSQL。