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

在数据库系统的设计与实现中，数据结构的选择直接影响存储效率、查询性能和并发控制能力。本文将系统梳理数据库中常用的8种核心数据结构，从基础存储结构到复杂索引机制，结合实际应用场景分析其设计原理与优化方向，为开发者提供技术选型参考。

一、数组（Array）：连续存储的基石

数组通过连续内存空间存储同类型数据，在数据库中主要用于固定列宽的表数据存储。例如，MySQL的InnoDB引擎在处理定长字段（如INT、CHAR(10)）时，会采用类似数组的结构组织页内数据。其优势在于随机访问效率高（O(1)时间复杂度），但插入删除需移动数据，导致性能下降。

优化实践：

1. 结合页（Page）机制使用，如InnoDB默认16KB页，每页存储多行数据
2. 配合变长字段处理技术（如MySQL的行溢出机制）解决数组长度固定问题
3. 在内存数据库（如Redis的ZipList）中，数组结构可提升紧凑存储效率

二、链表（Linked List）：动态扩展的解决方案

链表通过指针连接非连续节点，在数据库中常用于动态增长的数据存储。例如，PostgreSQL的TOAST机制处理大对象时，会将数据分割为多个链表节点存储。其优势在于插入删除高效（O(1)时间复杂度），但随机访问需遍历链表（O(n)）。

应用场景：

• 数据库日志文件的链式存储
• 内存表中的变长字段存储
• 分布式数据库中的分片数据链接

三、哈希表（Hash Table）：精准定位的利器

哈希表通过哈希函数将键映射到存储位置，在数据库中主要用于等值查询优化。例如，Redis的K-V存储、Memcached的核心数据结构均采用哈希表。其优势在于查询效率高（平均O(1)），但存在哈希冲突问题。

冲突解决策略：

1. 链地址法：如MySQL的哈希索引使用链表处理冲突
2. 开放寻址法：如Redis的字典实现采用二次探测法
3. 动态扩容机制：当负载因子超过阈值（如0.75）时进行rehash

四、B树与B+树：磁盘I/O的优化大师

B树及其变种B+树是数据库索引的核心结构，通过多路平衡搜索树特性，将随机I/O转化为顺序I/O。InnoDB的聚簇索引、MySQL的MyISAM索引均采用B+树。其关键特性包括：

1. 节点大小等于页大小（如16KB），最大化单次I/O读取的数据量
2. B+树所有数据存储在叶子节点，且通过双向链表连接，支持高效范围查询
3. 分支因子优化：通常选择200-300的分支数，平衡树高度与节点填充率

性能对比：
| 结构 | 查询效率 | 范围查询 | 空间利用率 |
|————|—————|—————|——————|
| B树 | O(log n) | 需回溯 | 中等 |
| B+树 | O(log n) | 高效 | 高 |

五、红黑树（Red-Black Tree）：内存中的平衡专家

红黑树作为自平衡二叉搜索树，在数据库中主要用于内存索引结构。例如，Java的TreeMap、C++的STL map均基于红黑树实现。其通过5条规则（根节点黑、红节点子节点黑、路径黑节点数相同等）保证最坏情况下O(log n)的查询效率。

与AVL树对比：
| 特性 | 红黑树 | AVL树 |
|——————|————————-|————————|
| 平衡度 | 近似平衡 | 严格平衡 |
| 插入删除 | 更快（旋转少） | 较慢（旋转多） |
| 查询效率 | 略低 | 更高 |

六、跳表（Skip List）：概率平衡的革新者

跳表通过多层链表结构实现概率平衡的搜索树，在LevelDB、Redis的有序集合中广泛应用。其核心思想是通过随机层数减少搜索路径，平均查询效率为O(log n)，且实现简单于树结构。

实现要点：

1. 节点层数随机生成（如通过抛硬币决定）
2. 最高层数控制为log₂n
3. 支持动态插入删除，无需复杂旋转操作

七、LSM树（Log-Structured Merge-Tree）：写优化的典范

LSM树通过内存缓冲+磁盘分层合并机制，将随机写转化为顺序写，在RocksDB、Cassandra等数据库中实现高吞吐写入。其工作流程包括：

1. 内存表（MemTable）接收写请求（采用跳表或B树结构）
2. 当MemTable达到阈值时，冻结为不可变的Immutable MemTable
3. 后台线程将Immutable MemTable刷盘为SSTable（Sorted String Table）
4. 定期执行Compaction操作合并多个SSTable

性能优势：

• 写入吞吐量比B树高10-100倍
• 适合写密集型场景（如时序数据库）
• 通过Bloom Filter减少磁盘I/O

rage-">八、列式存储结构（Columnar Storage）：分析型数据库的核心

列式存储将数据按列组织，在ClickHouse、Vertica等分析型数据库中实现高效压缩与向量查询。其关键技术包括：

1. 列组（Column Group）：将经常联合查询的列存储在一起
2. 字典编码：对低基数列建立字典映射，减少存储空间
3. 位图索引：为分类列构建位图，加速WHERE条件过滤
4. 向量化执行：按列批量处理数据，提升CPU缓存利用率

与行式存储对比：
| 场景 | 列式存储 | 行式存储 |
|———————|—————————-|—————————-|
| OLAP查询 | 快（只读取必要列）| 慢（需全行扫描） |
| OLTP事务 | 慢（单列更新代价高）| 快（行级锁定） |
| 压缩率 | 高（同值连续） | 低 |

总结与选型建议

数据库数据结构的选择需综合考虑读写比例、查询模式、数据规模三大因素：

1. 高并发写入场景：优先选择LSM树（如RocksDB）
2. 点查询密集场景：哈希表或B+树索引（如MySQL）
3. 范围查询场景：B+树或列式存储（如PostgreSQL）
4. 内存数据库场景：跳表或红黑树（如Redis）
5. 分析型查询场景：列式存储+位图索引（如ClickHouse）

开发者在实际应用中，往往需要组合使用多种数据结构。例如，InnoDB同时使用B+树索引（聚簇索引）、哈希索引（自适应哈希索引）和LSM树思想（Change Buffer）。理解这些数据结构的底层原理，能够帮助开发者在数据库设计、索引优化和查询调优中做出更科学的决策。