为什么低选择性列上的索引会损害查询性能

Question

表很简单：

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+tree 中。因此，使用列上的索引name，MySQL 将知道哪些行满足name=5。然后 MySQL 将这些行提取到结果集中。我认为上面的过程会比扫描整个表格更快（但我错了）。所以我想问的是哪个进程使得（例如，从磁盘加载索引到内存，在B+树中搜索等）索引扫描比全表扫描慢。

此外，我知道如果表更大，性能差异会更大（我仍然想知道为什么）。

我将非常感谢您的帮助！
谢谢！

Answer 1

使用非聚集索引访问行，即idx_name需要额外的随机 I/O：b 树查找找到聚集（主键）索引值，然后您需要从聚集索引中获取实际行。

另一种方法是对聚集索引本身进行顺序扫描，这不会产生额外的 I/O 成本，而且通过顺序而不是随机来提高效率。