此sql查询的搜索时间复杂性

Question

本表提供了有关房地产的信息。列“类型”包含“公寓”、“房屋”、“乡镇住宅”或“别墅”的值。每种类型的条目数大约占表中条目总数的25%。

表名、列名、数据类型、RealEstate ID、DEC(10)类型、VARCHAR(40)、Price DEC(10、2)大小DEC(4)典型的查询要求所有给定类型的不动产:从RealEstate中选择ID，其中为该表定义了Type =‘House’两个索引。第一个索引是为“ID”列定义的，第二个索引是为“类型”列定义的。相对于条目数n和结果集m的大小，这个查询的时间复杂度是多少？

时间复杂度为O (log(n)+m)或O(n)？

Answer 1

这是非常粗略的说法，在某种程度上是一种推测：

复杂性应该是O(m)，因为由于存在索引，

DB引擎可以找到/找到匹配Type = 'House'的记录。

在固定的时间内。所以这里所花费的时间就是处理

匹配计数为m的记录(例如读取它们并返回)

打电话的人)。因此，复杂度是O(m)，因为处理

与返回的记录的数量成正比。

但如果从较低的角度来看，我想这也取决于许多其他因素：

如果您的索引维护良好(不是分段的)，则如果记录位置良好。

在磁盘上(例如顺序)等，所以很难给出一个直接的/简单的

大O公式。

Answer 2

时间复杂度可能是O(n)。

这个问题是另一种提问方式：“这个查询是使用索引扫描还是全表扫描？”通常，索引范围扫描在查找一小部分行时工作得更好。而且，一般来说，当查找大量行时，全表扫描工作得更好。

没有一个“神奇数字”。但根据我的经验，对于任何一个显着大小的表格，25%肯定是在完整的表格扫描区域。

这个决定取决于许多因素:缓存、多块读取计数、物理存储、统计(对象和系统)、群集因素(行存储在磁盘上的情况如何--因为Oracle每次检索一个块可能需要读取100%的块才能读取1%的数据)，等等。

码样例

下面是一个简单的示例演示，一个完整的表扫描。注意，我使用的是100000行。如果问题是关于一个只有少数行的表，那么复杂性就无关紧要了，因为常数开销将比算法更重要。

create table RealEstate
(
    ID       DEC(10),
    Type     VARCHAR(40),
    Price    DEC(10,2),
    the_Size DEC(4)
);
create index RealEstate_idx on RealEstate(type);

insert into RealEstate
select level, decode(mod(level, 4), 0, 'Apartment', 1, 'House', 2, 'Townhouse', 3, 'Villa') , 100, 100
from dual connect by level <= 100000;
begin
    dbms_stats.gather_table_stats(user, 'realestate');
end;
/

执行计划

注意TABLE ACCESS FULL。

explain plan for select * from RealEstate where type = 'House';
select * from table(dbms_xplan.display);


Plan hash value: 4238863598

--------------------------------------------------------------------------------
| Id  | Operation         | Name       | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |            | 25000 |   463K|   103   (1)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| REALESTATE | 25000 |   463K|   103   (1)| 00:00:01 |
--------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter("TYPE"='House')