假设有一个表 T，其列 C 由 B 树索引，并且给定常数 k。假设以下查询的结果为 n：
select count(*) from T where C > k;
我在 MySQL(InnoDB) 中尝试过这样的查询，C 列由 B-tree 索引，并意识到 n 的值越大，查询越慢。在一张大桌子（GB）上，我什至不得不等待几分钟。因此，我推测时间复杂度与 n 成线性关系。但我知道是否有人在 B-Tree 内部节点上存储聚合信息，这些信息可以在相对于表大小的对数时间内完成。
任何人都可以建议任何实施对数解决方案的 DBMS，或者任何减少 MySQL 查询时间的技巧吗？
在看到执行计划之前，你什么也说不出来。至少在 Oracle 中，您还应该在 C 列上有直方图，以便对不同的 C 值有不同的执行计划。
索引的深度通常为3-5。对数的底非常大。还要记住，许多数据库在从表中删除行时会作弊，通常叶节点可能指向已删除的行。在 B-tree 中维护聚合值是不值得的，它不会很好地扩展。
如果您正在寻找具有各种精美索引选项的数据库，请查看 PostreSQL。
是的，所有 DBMS 都支持索引。确保所有 K 字段都已编入索引，据我所知，这是您基本上可以做的唯一一件事。
此链接适用于 SQL Server，但它应该适用于 MySql（只需很少的修改）。
不确定，但这个问题看起来与SO 上的这个问题有关。