小孟的技术笔记

Appearance

61. 跳表（Skip List）和 B+树（B+ Tree）的区别 ​

跳表（Skip List） ​

一、是什么？ ​

跳表是一种基于多层有序链表的随机化数据结构，通过建立多级索引加速查找。每个节点包含多个指向不同层级后继节点的指针，形成“跳跃”式查询路径。

二、解决什么问题 ​

解决有序链表查询效率低（O(n)）的问题，提供接近平衡树的查询性能（平均 O(log n)），同时实现更简单。

三、核心方法 ​

  1. search()：从顶层索引开始逐层向下查找
  2. insert()：插入节点并随机生成层数（抛硬币算法）
  3. delete()：删除节点并更新索引指针

四、应用场景 ​

  • Java 的 ConcurrentSkipListMap 和 ConcurrentSkipListSet（JDK6+）
  • 内存数据库索引（如 Redis ZSET）
  • 需要高并发读写的场景（跳表天然支持无锁并发）

五、Java 示例 ​

java
ConcurrentSkipListMap<Integer, String> skipList = new ConcurrentSkipListMap<>();
skipList.put(3, "Apple");
skipList.put(1, "Banana");
skipList.put(2, "Cherry");

System.out.println(skipList.get(2));  // 输出 Cherry
System.out.println(skipList.ceilingKey(1)); // 输出 1（范围查询）

六、重要注意事项 ​

  1. 空间开销较大（索引层占用额外空间）
  2. 性能依赖随机层数生成，最坏复杂度 O(n)
  3. JDK 的实现是线程安全的

B+树（B+ Tree） ​

一、是什么？ ​

B+树是一种多路平衡查找树，所有数据存储在叶子节点，内部节点仅存键值（索引）。叶子节点通过指针形成有序链表。

二、解决什么问题 ​

解决磁盘 I/O 效率问题：通过增加节点分支因子降低树高，减少磁盘访问次数（典型应用在数据库索引）。

三、核心特征 ​

  1. 所有数据在叶子节点，内部节点仅存索引
  2. 叶子节点形成双向链表（高效范围查询）
  3. 节点填充因子通常 >50%（如 MySQL InnoDB 的 15/16）

四、应用场景 ​

  • 数据库索引（MySQL InnoDB、Oracle）
  • 文件系统（NTFS、ReiserFS）
  • 大数据存储（HBase、LevelDB）

五、重要注意事项 ​

  1. 节点分裂/合并成本高
  2. 内存不足时性能急剧下降
  3. Java 标准库无内置实现，需第三方库（如 Apache Commons Collections）

关键区别（对比表） ​

特性跳表 (Skip List)B+树 (B+ Tree)
数据结构多层链表多叉平衡树
查询复杂度平均 O(log n)，最坏 O(n)稳定 O(log n)
插入/删除成本低（只需更新局部指针）高（可能触发节点分裂/合并）
空间占用高（额外索引层）低（填充因子高）
范围查询效率中等（需遍历链表）极高（叶子节点直接链表访问）
磁盘友好性差（内存数据结构）极优（节点大小=磁盘页）
并发控制天然支持无锁并发（如 CAS）需额外锁机制
Java 实现ConcurrentSkipListMap (JDK6+)无标准库实现
适用场景内存数据库、高并发缓存磁盘数据库、文件系统

总结 ​

  1. 内存 vs 磁盘：

    • 跳表适合内存操作（Java 并发集合）
    • B+树专为磁盘存储优化（数据库索引）

  2. 复杂度稳定性：

    • B+树提供稳定 O(log n) 操作
    • 跳表最坏情况可能退化（但概率极低）

  3. 工程选择建议：

    • 需要高并发内存索引 → 选跳表（ConcurrentSkipListMap）
    • 需持久化存储/范围扫描 → 选 B+树（如数据库场景）

💡 JDK 提示：Java 的跳表实现自 JDK6 引入，在并发场景下比 TreeMap（红黑树）性能更优，尤其适合现代多核处理器环境。