为什么我们使用 B+ 树来做聚簇索引而不是散列？

Question

在MySQLInnoDB 或许多其他数据库引擎中，主键是通过聚集索引实现的。但是，在使用二级索引进行搜索后，引擎必须使用二级索引中提供的主键查找聚簇索引（如果没有覆盖索引）。

InnoDB的聚簇索引使用B+树，是一种搜索复杂度O(log n)的结构，所以我们可以总结如下过程：

使用聚簇索引：一次通过，费用O(n).
使用二级索引：两次传球。第一次通过花费 O(log n) 个结果 m 条记录。那么第二遍m条记录每条花费O(log n)，所以时间复杂度为m*O(log n).

我知道使用hasing时，搜索的时间复杂度可以降低到O(1)，所以我想知道为什么这些数据库引擎更喜欢使用B+树而不是hasing技术（例如构建KV存储）？是不是因为记录是存储在磁盘而不是内存中？

同时，我还有一个问题，其他一些数据库，比如RocksDB，使用的是KV存储，而不是B+树。他们为什么使用它？

编辑

我想把问题说清楚一点。我发现很多表格都是用 auto increment PK 设计的，而不是使用具有实际意义的东西，比如 phone 数字或 IP。所以B+树的优势没有被充分发挥出来。比如B+树擅长在范围内搜索数据，但是我在实践中搜索一个auto increment PK在范围内是很少见的

Answer 1

高效的散列需要对密钥的类型、数量和分布有一些先验知识。加上处理冲突的复杂性（两个键以相同的散列值结尾）。 Space 必须预先分配，并且可能太小而很快运行出来，或者太大导致大量资源浪费。

b 树在很小的时候很有效，并且可以增长到任何大小，只要有可用的磁盘 space。

你引用了操作的数量，但是 b-trees 使用简单的比较便宜，哈希使用昂贵的复杂算法。因此，在 64,000 条记录的数据库中查找记录位置的七八次比较，可能比计算哈希值使用更少 cpu。

Answer 2

B-tree 索引的一个重要特征是所谓的range scan. Hash 索引没有那个特征。较旧的 MySQL table 引擎 MyISAM 的名称提供了一个线索。它代表索引顺序访问方法。 BTREE索引的固有排序是一大特点。

如果我们有一个 table credit，例如，包含 credit_id、user_id、datestamp 和 amount 列，我们可能会使用这个查询。

SELECT SUM(amount) amount FROM credit 
 WHERE datestamp >= CURDATE() - INTERVAL 7 DAY
   AND datestamp <  CURDATE();

在 (datestamp, amount) MySQL 上使用两列 BTREE 索引可以随机访问索引 O(log n) 到第一个符合条件的日期戳，然后为每个连续的符合条件的日期戳顺序访问它 O(1)。并且，因为amount在索引中，所以MySQL完全可以满足从索引上查询。（它被称为 covering index）。 InnoDB 索引隐式包含主键列，即包含所有 table 数据的聚集索引的键。

大多数大型生产 table 都为它们定义了多个覆盖索引，选择这些索引是为了加速在特定应用程序中花费最多时间的查询。

我并不是说 HASH 索引没有用。离得很远。但很明显，如果没有 BTREE 索引，MySQL 的工作效率会低得多。

（InnoDB 引擎的代码对插入具有自动递增主键的行进行了许多优化。如果应用程序使用其他东西（如随机 guid）作为主键，它可能会破坏这些优化。）

为什么我们使用 B+ 树来做聚簇索引而不是散列？

Why we use B+ tree for clustered index rather than hashing?

mysql

database

indexing

innodb