B+ 树与跳表：数据库索引结构的性能权衡

B+ 树与跳表是数据库与 KV 存储中最常用的两种有序索引结构，其设计取舍直接决定了读写性能特征。

一、B+ 树特点

• 多路平衡树，非叶节点仅存储键，扇出大、树高低
• 所有数据集中在叶子节点，并通过链表相连，适合范围查询
• 原地更新，写放大较低，但随机写引发页分裂

二、跳表特点

• 基于多层链表实现，查找、插入、删除平均 O(log n)
• 实现简单，无需复杂平衡操作
• 范围查询友好，常用于 Redis ZSet 与 LevelDB MemTable

typedef struct skiplistNode {
    double score;
    struct skiplistNode *backward;
    struct skiplistLevel {
        struct skiplistNode *forward;
        unsigned long span;
    } level[];
} skiplistNode;

磁盘存储倾向 B+ 树（减少 I/O 次数），内存存储倾向跳表（实现简单、并发友好）。