主页 / dba / 问题 / 38717
Accepted
Juan Carlos Coto
Asked: 2013-03-28 12:26:31 +0800 CST

大于或小于索引查询的 PosgtreSQL 的算法复杂度是多少（与相等性相比）？

  • 772

假设列idx_int上有一个索引int_col，这样的查询的算法复杂度是多少？

SELECT id FROM table
    WHERE table.int_col > 1;

我特别想知道查询是否比执行相等子句效率低得多（如果我理解正确的话是 O(log N)）。我很确定它们都可以使用 B 树，所以我希望它们在复杂性/效率方面大致相同。

非常感谢！

postgresql index

1 个回答

  1. Best Answer

    我不知道 PostgreSQL 引擎，但是在现实世界中，做

    WHERE X > y

    将导致引擎查找 B 树索引中的点 where X = y，然后扫描其余数据以返回相关行。有了足够的数据，返回将需要很长时间。

    显然，WHERE X = y将返回得更快，因为它只需要返回一行，只需要初始的查找操作。

    当然，这是假设X已编入索引。

    • 1

相关问题