唯一的聚集索引是否提供類似數組的查找性能？

假設我有一個具有唯一整數索引的 MySQL 表，該索引id為每一行自動遞增。

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

假設我主要對優化通過唯一索引查找行的查詢感興趣。例如：

SELECT PlanetName FROM Planets WHERE id = 2

如果我正在使用另一種語言進行程式，並且我將數據載入到一個數組中，那麼通過指針算法執行這些查找會非常快。當我在 MySQL 中執行查詢時，我希望能夠獲得相同的性能。

我的想法是：

• 聚集索引意味著數據是按順序儲存的（即，與原始數組在記憶體中的儲存方式非常相似）
• 唯一的整數索引確保 SQL 不必擔心重複行

那麼，如果我為 建立一個唯一的聚集索引id，這是否意味著 MySQL 將執行一個指針算術類型的查找？

是和不是。

程式語言中的“數組”執行一些簡單的地址算術來快速定位數組中的第 N 個條目。

在 MySQL 中，大多數索引都建構為 B+Trees。（參見維基百科）這種結構比數組更複雜，但仍然是最好的。 WHERE id=2需要向下鑽取節點的“樹”以在“id”列中找到帶有“2”的項目。

與簡單數組相比，BTree 有幾個優點。而這些優勢對於數據庫操作的通用性是必要的。

• 數據庫表旨在處理任意數量的項目。數組僅限於 RAM 中可以容納的內容。 這有效地防止了數組的地址算術，並強制執行一些其他實現。
• 你可以DELETE * FROM t WHERE id=2。（數組不允許空洞；BTrees 允許。）請注意，它阻止使用“地址算術”來定位記錄。
• BTree 索引可以使用字元串進行查找—— WHERE name = 'Venus'。這與使用數字一樣容易且幾乎一樣快。
• 由於 BTree 是“塊”；他們四處散落，他們可能會變得空虛。這導致維護樹的成本。不用擔心這個；平均而言，BTree 仍然非常快。
• 在這種情況下，“分群”意味著 ids 1,2,3,… 在某種意義上是“連續的”和“相鄰的”。（或“1,3,…”，如果 id=2 已被刪除。）實際上，一個 B+Tree 塊中大約有 100 個連續值。這允許“範圍”非常有效。範例： WHERE name BETWEEN 'Mars' AND 'Venus'將按字母順序儲存。
• 當“範圍”查詢超出 B+Tree 塊的末尾時，下一個塊將從它連結。（這是“+”。）
• 從技術上講，數組查找是 O(1)，而 BTree 查找是 O(logN)。但是日誌並不是一個很大的數字——一百萬行的 BTree 大約有 3 級深；對於一萬億行，只有大約 6 層深。也就是說，在萬億行表中查找一行的速度只有在百萬行表中的兩倍左右。
• MySQL（特別是 InnoDB）需要一個唯一的PRIMARY KEY並將其與數據聚集在一起。
• 因此，通過 PK（WHERE id=2如果id是 PK）進行查找是對一個 BTree 的向下鑽取以獲取整行。
• 二級索引（不是 PK）作為 B+Tree 實現，具有鍵列和 PK 的列。
• 因此，通過輔助鍵（SELECT * FROM t WHERE name='Venus'with INDEX(name)）查找要復雜一些。首先向下鑽取name索引以找到id，然後向下鑽取 PK+data BTree 以找到整行。
• 防止重複——這發生在何時INSERTing或UPDATEing連續發生。PRIMARY KEY實際上，它通過（如果給定 – cf AUTO_INCREMENT）和每個UNIQUE索引查找行。如果其中任何一個匹配，則會出現錯誤（除非執行INSERT IGNORE）。否則，PK 的 BTree 和 Unique BTrees 準備採用新的/修改的行。處理潛在的重複不是免費的，而是便宜的。
• 對於 a BETWEEN，訪問第一行 (O(logN))，然後每個後續行都是 O(1)。

所以，是的，數組查找需要納秒，這比數據庫查找要快，數據庫查找需要微秒（如果記憶體在 RAM 中）或毫秒（如果需要 I/O）。這是您必須為無限大小和更多功能付出的代價。

引用自：https://dba.stackexchange.com/questions/259603