哈希表、跳表还是 B+ 树：怎么选

选哈希表、跳表还是 B+ 树，其实就看两件事：数据放哪、怎么查。

数据全在内存里，又只按 key 精确找，直接上哈希表。算个哈希跳过去就行，O(1) 最快。但它把顺序打散了，一旦要范围查询，它直接出局。

要是内存里既要按 key 找，又要按顺序取一段，跳表最合适。它在有序链表上建多级索引，查找 O(log n)，范围查询顺着底层扫过去就行。实现比红黑树简单得多，局部修改还容易无锁化。Redis 的 ZSet 就是用它。

数据放到磁盘上，B+ 树是默认选项。它的非叶子节点只存 key，一个 16KB 的页能塞下上千个索引项，树只有三四层高。叶子节点串成链表，范围查询变成顺序读，正好压住机械硬盘的寻道瓶颈。

不过磁盘还得细分。SSD 没有机械寻道，但原地更新代价高，容易写放大。读多写少照样用 B+ 树；写入密集的话，就得考虑 LSM-Tree 或者改造过的 B+ 树了。