数据库中常用的8种数据结构！

数据库系统的性能与稳定性高度依赖于底层数据结构的选择。从内存缓存到磁盘存储，从索引构建到事务处理，每种数据结构都承载着特定的设计目标。本文将系统梳理数据库领域最常用的8种数据结构，解析其技术原理、应用场景及优化策略，帮助开发者深入理解存储引擎的设计哲学。

一、哈希表（Hash Table）

哈希表通过哈希函数将键映射到存储位置，实现O(1)时间复杂度的查找。在数据库中，哈希表主要用于内存缓存（如Redis的键值存储）和哈希索引（如MySQL的MEMORY引擎）。

技术实现要点：

• 哈希冲突处理：采用链地址法或开放寻址法
• 动态扩容机制：当负载因子超过阈值时触发rehash
• 哈希函数选择：MurmurHash、CityHash等非加密哈希算法

应用场景：

-- MySQL MEMORY引擎的哈希索引示例
CREATE TABLE user_cache (
    id INT PRIMARY KEY,
    name VARCHAR(100)
) ENGINE=MEMORY;

优化建议：

• 对范围查询不友好的特性限制了其在磁盘索引中的应用
• 适用于等值查询密集的场景，如会话管理、计数器

二、B+树（B+ Tree）

作为关系型数据库索引的默认选择，B+树通过多路平衡搜索树结构实现高效的磁盘I/O优化。其所有数据存储在叶子节点，形成有序链表，支持高效的范围查询。

核心特性：

• 节点大小匹配磁盘块（通常4KB）
• 扇出系数（fan-out）通常在100-200之间
• 叶子节点通过指针连接形成有序链表

InnoDB引擎实现细节：

// 简化版B+树节点结构
typedef struct bplus_node {
    bool is_leaf;
    int key_count;
    int keys[MAX_KEYS];  // 排序后的键
    void* children[MAX_CHILDREN];  // 子节点指针
    void* records[MAX_LEAF_RECORDS];  // 叶子节点记录
} BPlusNode;

性能优势：

• 磁盘I/O次数与树高度成正比（通常3-4次）
• 支持高效的范围扫描和排序操作

三、LSM树（Log-Structured Merge-Tree）

针对写密集型场景优化的LSM树，通过内存缓冲和分层合并机制实现高吞吐写入。其核心思想是将随机写入转化为顺序写入。

工作原理：

1. 写入首先进入内存的MemTable（跳表实现）
2. 当MemTable达到阈值时，刷盘为不可变的SSTable
3. 后台进程执行compaction合并多个SSTable

RocksDB实现示例：

// RocksDB的LSM树结构
rocksdb::Options options;
options.create_if_missing = true;
rocksdb::DB* db;
rocksdb::DB::Open(options, "/path/to/db", &db);
// 写入操作
rocksdb::Status s = db->Put(rocksdb::WriteOptions(), "key1", "value1");

适用场景：

• 时序数据库（InfluxDB）
• 大数据存储系统（HBase）
• 高频写入场景（如日志收集）

四、红黑树（Red-Black Tree）

作为自平衡二叉搜索树，红黑树通过严格的着色规则和旋转操作保持O(log n)的查找、插入和删除复杂度。在数据库中主要用于内存中的有序数据管理。

特性分析：

• 每个节点是红色或黑色
• 根节点和叶子节点（NIL）为黑色
• 红色节点的子节点必须为黑色
• 从任一节点到其每个叶子节点的路径包含相同数量的黑色节点

PostgreSQL的内存结构应用：

// PostgreSQL的TupleSort使用红黑树管理排序元组
typedef struct SortTuple {
    Datum values[INDEX_MAX_KEYS];
    bool isnull[INDEX_MAX_KEYS];
    int tuple_position;
} SortTuple;

五、跳表（Skip List）

通过多层链表结构实现概率平衡的跳表，在内存中提供接近O(log n)的复杂度，同时代码实现比平衡树更简单。Redis的ZSET就是典型应用。

结构组成：

• 第0层包含所有元素的有序链表
• 每上升一层，节点数量约为下一层的1/2
• 每个节点包含指向后方各层节点的指针

Redis实现示例：

// Redis跳表节点结构
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

六、R树（R-Tree）

针对空间数据设计的R树，通过最小边界矩形（MBR）组织多维数据，广泛应用于地理信息系统（GIS）和空间数据库。

核心操作：

• 查找：通过矩形相交测试定位候选节点
• 插入：选择最小覆盖矩形增益最小的路径
• 删除：直接删除后调整父节点矩形

PostGIS的空间索引示例：

-- 创建R树索引
CREATE INDEX idx_spatial ON locations USING GIST (geom);
-- 空间查询
SELECT * FROM locations 
WHERE ST_DWithin(geom, ST_GeomFromText('POINT(1 1)', 4326), 0.1);

七、位图索引（Bitmap Index）

位图索引通过位图向量表示列值的存在性，特别适合低基数列（如性别、状态）的查询优化。Oracle和SQLite等数据库支持这种索引类型。

实现原理：

• 每个唯一值对应一个位图
• 位图中1表示该行包含该值，0表示不包含
• 逻辑运算（AND/OR）实现多条件查询

性能特点：

• 压缩率高（通常可压缩到原数据的1/10）
• 适合读多写少的场景
• 不适合高基数列（会导致位图过大）

八、倒排索引（Inverted Index）

全文检索系统的核心数据结构，通过词项到文档ID的映射实现快速文本检索。Elasticsearch和Solr等搜索引擎都基于这种结构。

结构组成：

• 词典：存储所有词项及其元数据
• 倒排列表：记录包含该词项的文档ID、位置信息等
• 压缩技术：Delta编码、PForDelta等压缩算法

Elasticsearch实现示例：

// 倒排索引的简化表示
{
  "terms": {
    "database": {
      "docs": [1, 3, 5],
      "positions": [[2], [5], [1]]
    },
    "structure": {
      "docs": [2, 3, 4],
      "positions": [[3], [1], [4]]
    }
  }
}

实际应用中的组合策略

现代数据库通常组合使用多种数据结构：

1. InnoDB：B+树索引 + 哈希索引（自适应） + 红黑树（内存管理）
2. RocksDB：LSM树 + 布隆过滤器 + SSTable索引
3. Elasticsearch：倒排索引 + BKD树（数值字段） + 文档值（列式存储）

优化建议：

• 根据查询模式选择索引类型：等值查询优先哈希，范围查询优先B+树
• 考虑写入频率：高频写入场景考虑LSM树
• 评估数据维度：空间数据使用R树，文本数据使用倒排索引
• 监控索引效率：定期分析未使用的索引

未来发展趋势

随着硬件技术的演进，新型数据结构不断涌现：

• Paxos存储引擎：结合LSM树和B+树优势
• 学习索引：使用机器学习模型替代传统树结构
• 持久化内存：优化内存数据结构的持久化方案

理解这些核心数据结构的工作原理和适用场景，是进行数据库性能调优、架构设计和故障排查的基础。开发者应根据具体业务需求，在写入吞吐量、查询延迟、存储效率等维度进行权衡选择。