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

数据库系统的性能与稳定性高度依赖于底层数据结构的选择与设计。从存储引擎到查询优化器，从索引构建到事务管理，数据结构贯穿了数据库的每一个核心模块。本文将系统梳理数据库系统中常用的8种数据结构，结合其数学原理与工程实践，为开发者提供深入的技术洞察。

一、B树与B+树：磁盘I/O优化的典范

作为关系型数据库索引的核心结构，B树及其变种B+树通过平衡多路搜索树的特性，将磁盘I/O次数控制在O(log n)级别。以MySQL InnoDB引擎为例，其主键索引采用B+树结构，每个节点大小设计为16KB（可配置），通过填充因子控制节点分裂时机。这种设计使得单次I/O能加载数百个键值对，相比二叉搜索树的O(log n)次I/O（每次仅加载1个键值），性能提升达数十倍。

B+树与B树的关键区别在于：B+树将数据全部存储在叶子节点，并通过双向链表连接，这使得范围查询效率显著提升。例如执行SELECT * FROM users WHERE age BETWEEN 20 AND 30时，数据库只需定位到第一个符合条件的叶子节点，然后顺序遍历链表即可，无需回溯父节点。

二、哈希表：内存中的极速查找

在内存数据库（如Redis）和缓存系统（如Memcached）中，哈希表通过O(1)的查找复杂度实现极致性能。Redis的字典结构采用SipHash算法生成哈希值，通过动态扩容机制（当负载因子超过1时）维持查找效率。其实现包含两个层次的哈希表，扩容时新建表并渐进式迁移数据，避免服务阻塞。

哈希表的局限性在于不支持范围查询和有序遍历。为此，Redis通过ZSET结构（跳表+哈希表）实现有序集合，在保持O(log n)查找复杂度的同时支持范围操作。例如执行ZRANGEBYSCORE leaderboard 90 100时，跳表能快速定位到分数区间。

三、LSM树：写优化的存储引擎

针对高并发写入场景，LevelDB、RocksDB等存储引擎采用LSM树（Log-Structured Merge-Tree）架构。其核心思想是将随机写入转化为顺序写入：数据先写入内存的MemTable（跳表实现），当MemTable达到阈值时转为不可变的Immutable MemTable，并异步刷盘到SSTable（Sorted String Table）。

这种设计使得写入吞吐量提升数个量级，但读取时需要合并多个SSTable的数据。为此，LSM树通过分层合并策略（Level 0到Level n）控制文件数量，并维护布隆过滤器加速存在性判断。例如在TiDB中，LSM树与B+树结合使用，底层存储采用LSM树优化写入，上层索引使用B+树加速查询。

四、跳表：有序数据的平衡之选

跳表通过多层链表结构实现有序数据的快速查找，其平均查找复杂度为O(log n)，空间复杂度为O(n)。Redis的有序集合（ZSET）和LevelDB的MemTable均采用跳表实现。跳表的优势在于实现简单，无需复杂的树旋转操作，且支持并发访问。

以Redis的ZSET为例，其跳表实现包含以下关键设计：

1. 层数随机生成（每层概率1/4）
2. 双向链表支持反向遍历
3. 分数与成员对象分离存储
4. 跨层指针优化查找路径

这种设计使得ZADD、ZREM等操作的时间复杂度均为O(log n)，且支持范围查询如ZREVRANGE。

五、倒排索引：全文检索的基石

在Elasticsearch、Solr等搜索引擎中，倒排索引（Inverted Index）通过词项到文档的映射实现快速全文检索。其核心结构包含：

1. 词典：存储所有词项，通常采用FST（Finite State Transducer）压缩存储
2. 倒排列表：记录包含词项的文档ID及位置信息
3. 文档存储：保存原始文档内容

例如，当用户搜索”database design”时，系统首先在词典中定位两个词项，然后合并它们的倒排列表（使用跳表或B+树存储），最后通过TF-IDF算法排序结果。倒排索引的优化方向包括：

• 词典压缩（FST相比哈希表节省90%空间）
• 倒排列表压缩（Delta编码+PFOR压缩）
• 列式存储优化（Parquet格式）

六、R树：空间数据的索引利器

针对地理信息系统（GIS）和计算机图形学，R树通过最小边界矩形（MBR）组织空间对象。其结构类似于B树，但每个节点包含多个MBR，且支持重叠区域。PostGIS等空间数据库使用R树实现ST_Contains、ST_DWithin等空间查询。

R树的插入算法包含以下步骤：

1. 从根节点开始，选择需要扩展面积最小的子节点
2. 若子节点已满，则分裂为两个节点（使用线性分裂或二次分裂算法）
3. 递归向上调整父节点的MBR

例如查询”附近5公里的餐厅”时，R树能快速剪枝不相交的区域，仅访问可能包含结果的节点。

七、位图索引：低基数列的高效方案

在数据仓库和OLAP系统中，位图索引通过位串表示列值的出现情况。例如性别列（男/女）的位图索引包含两个位串：

• 男性位串：101010…
• 女性位串：010101…

这种设计使得WHERE gender = '男'查询转化为简单的位运算。位图索引的优化技术包括：

• 编码位图（BBC、WAH等压缩算法）
• 多列组合位图（Oracle的位图连接索引）
• 运行时合并（通过AND/OR操作组合多个位图）

位图索引的局限性在于高基数列（如用户ID）会导致位图过大，此时B树索引更为合适。

八、图数据结构：关联数据的自然表示

在Neo4j等图数据库中，图数据结构通过节点（Vertex）和边（Edge）的集合表示关联数据。其存储引擎通常采用以下设计：

1. 邻接表：每个节点存储其相邻节点列表
2. 邻接矩阵：适合稠密图，但空间复杂度高
3. 混合模式：结合邻接表与边索引

图数据库的查询优化重点在于图遍历算法（如DFS、BFS）和子图匹配。例如社交网络中的”好友推荐”功能，可通过共同好友数量计算相似度，这需要高效的三元组存储和遍历能力。

实践建议

1. 索引选择：高并发写入场景优先选择LSM树，低延迟读取场景选择B+树
2. 混合架构：结合多种数据结构，如TiDB的LSM树+B+树混合引擎
3. 监控优化：通过EXPLAIN分析查询计划，调整数据结构参数
4. 压缩技术：对历史数据采用列式存储+压缩算法（如ZSTD）
5. 分布式扩展：使用分片技术（如MongoDB的分片集群）横向扩展

数据库系统的性能优化是一个系统工程，数据结构的选择需结合业务场景、硬件配置和查询模式综合考量。理解这些核心数据结构的设计原理，能帮助开发者在架构设计阶段做出更优的决策，在运维阶段更高效地定位性能瓶颈。