1

这个问题更多的是理论上的性质：我有一个 SQL Server 2008 R2，其中一个数据库有一个表。该表由三列组成，第一列是主键，所有三列都有索引。

假设有 100 万条记录，我通过引用 WHERE 子句中的主键选择了一条记录。查询需要 1 秒才能完成。如果我再添加一百万条记录，查询需要多长时间？我假设通过在主键上有一个索引，主键对于所有记录都是唯一的，并且索引结构是一棵树，它应该类似于 O(n * log n)？

4

2 回答 2

4

在聚集索引上搜索一个条目是 B 树搜索，它是二叉树搜索。将记录数加倍意味着再进行一次半分裂迭代。

无论如何，索引搜索非常有效，并且处理它的额外 CPU 和 IO 的数量不是很多。

主键并不总是集群，但 SQL Server 默认会使其集群。其他 3 个索引在这里没有任何价值。

在这个演示脚本中，一百万行和两百万行都需要 3 页读取。查询计划是相同的，即使在 xml 中查看时也是如此

这表明索引树有空闲空间来处理额外的条目，并且需要一个数据页：整个表没有被缓存。

CREATE TABLE dbo.foo (ID int IDENTITY(1,1) PRIMARY KEY, Other1 int, Other2 char(10) DEFAULT 'abcdefghij', Other3 varchar(52) DEFAULT 'abcdefghijklmnopqrstuvwxyz');
GO
INSERT dbo.foo (Other1) VALUES (1);
GO
INSERT dbo.foo (Other1) SELECT Other1 FROM dbo.foo;
GO 20
SELECT COUNT(*) FROM dbo.foo;
GO

-- now enable viewing of execution plans

SELECT * FROM dbo.foo WHERE id = 456789
-- Table 'foo'. Scan count 0, logical reads 3, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
GO
-- double up rows
INSERT dbo.foo (Other1) SELECT Other1 FROM dbo.foo;
GO

SELECT * FROM dbo.foo WHERE id = 456789
-- Table 'foo'. Scan count 0, logical reads 3, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
GO
于 2013-07-12T09:35:48.157 回答
2

这取决于您的主键的大小 - 额外的百万行是否需要额外的索引结构级别或适合现有的级别数。

如果合适，您的查询不会减慢速度。

如果需要额外的级别，减速是搜索通过额外的级别，所以最多是级别数的百分比 - 如果它从 3 扩展到 4 - 最多是 25%。但它不会那么多，因为通过索引结构搜索只是过程的一部分，在叶级检索实际数据仍然需要时间。

自下而上：差异可能不存在或不应该引起注意（毫秒）。即使在具有数亿行的表中，基于 PK（聚集索引）选择行也应该是即时的。如果需要整整一秒钟，则可能是非常非常错误的事情。

于 2013-07-12T09:37:37.260 回答