mysql - 在包含 200 万条记录的表上添加索引是否会比包含 100 万条记录的同一张表慢两倍？

Question

我有一个包含 7000 万条记录的表，但缺少一个索引。我想计算加索引的时间，不备份表，在备份表上做索引。

我只是想知道它是否会慢两倍(线性)或者它是否是指数级的。

数据库:mysql 5.0

非常感谢

Answer 1

(免责声明:我对 MySQL 的经验很少)

它应该介于两者之间。

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

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

当然，事情并没有那么简单。计算索引树并不是真正的 CPU 繁重，并且由于索引页应该适合任何现代系统的 RAM，插入单个节点的操作 当树没有重新平衡时 将接近 O(1) time-wise:更新索引叶页的单个磁盘操作。

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

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

编辑:

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

底线:

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

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