在包含200万条记录的表格上添加索引的速度是具有100万条记录的同一表格的两倍吗？

Question

我有一个包含7000万条记录的表格,并且缺少索引.我想计算添加索引的时间,而不需要备份表并在备份表上执行索引.

我只是想知道它是慢两倍(线性)还是指数.

数据库:mysql 5.0

非常感谢

Answer 1

（免责声明：我对 MySQL 的经验很少）

它应该介于两者之间。

整个操作的复杂度绝对最低的是按顺序读取所有记录时出现的操作，这是一个线性过程 - O(n)。这是一个 I/O 绑定操作，对此无能为力 - 大多数操作系统中的现代缓存系统可能会有所帮助，但仅限于正在使用且适合可用内存的数据库。

在大多数 SQL 引擎中，索引是 B 树的某种变体。将单个记录插入到这样的树中的 CPU 复杂度大致为O(log(n))，其中n是其大小。对于n记录，我们得到的复杂度为O(n log(n))。操作的总复杂度应为O(n log(n))。

当然，事情并不那么简单。计算索引树实际上并不需要大量 CPU，而且由于索引页应该适合任何现代系统上的 RAM，因此在树未重新平衡时插入单个节点的操作在时间上接近于O(1)：单个磁盘操作更新索引的叶页。

然而，由于树确实得到了重新平衡，事情可能会更复杂一些。可能必须将多个索引页提交到磁盘，从而增加了必要的时间。作为粗略的猜测，我想说O(n log(n))这是一个好的开始......

不过，它永远不应该接近指数复杂度。

编辑：

我突然想到，实际上，内存缓存中可能装不下 70,000,000 个 B 树条目。这在很大程度上取决于索引的内容。INTEGER列可能没问题，但TEXT列完全是另一回事。如果平均字段长度为 100 字节（例如 HTTP 链接或 30 个非英语 UTF-8 文本字符），则需要超过 7GB 的内存来存储索引。

底线：

• 如果索引适合缓存，那么由于构建索引应该是单个数据库事务，因此它将受到 I/O 限制并且大致呈线性，因为必须解析所有记录，然后必须写出索引本身到永久存储。

• 如果索引不适合缓存，那么复杂性就会增加，因为每个操作都会涉及索引本身的 I/O 等待时间。