唯一的聚集索引是否提供类似数组的查找性能？

Question

假设我有一个具有唯一整数索引的MySQL表，该索引对于每一行都是自动递增的。

id | PlanetName
---+-----------
 0 | Mercury
 1 | Venus
 2 | Neptune

假设我主要对通过唯一索引查找行的查询进行优化。例如：

SELECT PlanetName FROM Planets WHERE id = 2

如果我用另一种语言编程，并将数据加载到数组中，那么通过指针算法执行这些查找将非常快。当我在MySQL中执行查询时，我希望能够获得相同的性能。

我的想法是：

• 聚集索引意味着按顺序存储数据(即，与原始数组存储在内存中的方式非常相似)。
• 唯一的整数索引确保SQL不必担心重复的行。

因此，如果我为id创建一个唯一的聚集索引，这是否意味着MySQL将执行指针算术类型查找？

Answer 1

是也不是。

编程语言中的“数组”执行一些简单的地址算法来快速定位数组中的Nth条目。

在MySQL中，大多数索引构建为B+Trees。(参见Wikipedia)这个结构比数组更复杂，但仍然是最好的。WHERE id=2需要向下钻取一棵“节点树”，以定位"id“列中的"2”项。

与简单的数组相比，BTree有几个优点。这些优点对于数据库操作的通用性是必不可少的。

• 数据库表设计用于处理任意数量的项目。数组仅限于可容纳在RAM中的部分。这有效地防止了数组的地址算法，并强制执行其他一些实现。
• 你可以DELETE * FROM t WHERE id=2。(数组不允许孔；BTrees允许。)请注意，它防止使用“地址算法”来定位记录。
• BTree索引可以使用字符串进行查找- WHERE name = 'Venus'。这和使用数字一样容易，而且速度也一样快。
• 因为BTrees是“块”；它们散落在周围，可能变得空空如也。这导致了维护树的开销。不要担心这一点；平均而言，BTrees仍然非常快。
• 这种情况下的“集群”意味着ids 1,2,3，.在某种意义上是“连续”和“相邻”。(如果id=2已被删除，则为"1,3，.“)实际上，在一个B+Tree块中有大约100个连续的值。这使得“范围”非常有效。示例：WHERE name BETWEEN 'Mars' AND 'Venus'按字母顺序存储。
• 当“range”查询从B+Tree块的末尾运行时，将从它链接下一个块。(这是“+”)
• 从技术上讲，数组查找是O(1)，BTree查找是O(logN)。但是日志没有那么大--一百万行的BTree大约有3层深；对于1万亿行，只有6层深。也就是说，在万亿行表中查找一行的速度仅是百万行表的两倍。
• MySQL (特别是InnoDB)需要一个唯一的PRIMARY KEY，并将其与数据聚在一起。
• 因此，PK的查找(WHERE id=2，如果id是PK)是一个BTree的向下钻取，以到达整个行。
• 次要索引(而不是PK)被实现为带有键列(S)和PK的列(S)的B+Tree。
• 因此，使用辅助键(SELECT * FROM t WHERE name='Venus'和INDEX(name))进行查找要复杂一些。首先向下钻取name索引以找到id，然后向下钻取PK+data BTree以查找整行。
• 防止重复--当INSERTing或UPDATEing行时发生这种情况。实际上，它通过PRIMARY KEY (如果给出- cf AUTO_INCREMENT)和每个UNIQUE索引来查找行。如果其中任何一个是匹配的，则会得到一个错误(除非执行INSERT IGNORE)。否则，PK的BTree和唯一的BTrees将采用新的/修改的行。对付潜在的欺骗不是免费的，而是廉价的。
• 对于BETWEEN，第一行被访问(O(logN))，然后每个后续行都是O(1)。

因此，是的，数组查找需要纳秒，这比数据库查找(如果缓存在RAM中)要快，或者毫秒(如果需要I/O )。这是你必须付出的代价，无限的大小和更多的功能。