為什麼低選擇性列上的索引會損害查詢性能

表很簡單：

CREATE TABLE `t1` (
 `ID` int NOT NULL AUTO_INCREMENT,
 `name` int DEFAULT '1',
 `LastName` int DEFAULT '0',
 UNIQUE KEY `idx_ID` (`ID`) USING BTREE,
 KEY `idx_name` (`name`)
) ENGINE=InnoDB;

DELIMITER $$
DROP PROCEDURE IF EXISTS populate_t1;
CREATE PROCEDURE populate_t1(IN num INT)
BEGIN
   DECLARE COUNT INT DEFAULT 0;
   WHILE COUNT < num DO
       INSERT INTO t1(`name`,`LastName`) VALUES(round(rand()+5, 0), round(rand()*10000, 0));
       SET COUNT = COUNT + 1;
   END WHILE;
END $$
DELIMITER ;

CALL populate_t1(1000000);
CREATE INDEX idx_name ON t1 (`name`);
OPTIMIZE TABLE t1;

該列的name選擇性非常低（即只有 2 個不同的值）。詢問

> SELECT * FROM t1 WHERE Name=5;
> OK, 499845 records, Time: 0.840s

會比使用全表掃描的查詢慢

> DROP INDEX idx_name ON t1;
> OK 
> SELECT * FROM t1 WHERE Name=5;
> OK, 499845 records, Time: 0.258s

這種性能下降是意料之中的，但我想弄清楚原因。

我知道該索引就像英語詞典前幾頁中的英語詞典索引。在我的範例中，索引儲存在 B+樹中。因此，使用列上的索引name，MySQL 將知道哪些行滿足name=5。然後 MySQL 將這些行提取到結果集中。我認為上面的過程會比掃描整個表格更快（但我錯了）。所以我想問的是哪個程序（例如，從磁碟載入索引到記憶體，在B+樹中搜尋等）索引掃描比全表掃描慢。

此外，我知道如果表更大，性能差異會更大（我仍然想知道為什麼）。

我將非常感謝您的幫助！

謝謝！

使用非聚集索引訪問行，即idx_name需要額外的隨機 I/O：b-tree 查找找到聚集（主鍵）索引值，然後您需要從聚集索引中獲取實際行。

另一種方法是對聚集索引本身進行順序掃描，它不會產生額外的 I/O 成本，而且由於是順序的，而不是隨機的，因此效率更高。

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