一个程序员拿到一台 16GB 内存的电脑，可以用十几种截然不同的方式把数据放进这 160 亿个字节里。选择哪种方式，决定了程序快还是慢、简单还是复杂，有时甚至决定了一个问题能不能被解决。
这些组织数据的方式，就叫数据结构。
破除误解：数据结构不是"存储格式"
很多人把数据结构理解为"把数据存到某种格式里"，比如把联系人存到 Excel 表格。这是过于狭窄的理解。
数据结构的核心不只是"怎么存"，而是"什么操作在什么代价下可行"。数组和链表存的数据可以完全相同，但"随机读取第 k 个元素"在数组里是 $O(1)$，在链表里是 $O(n)$；"在中间插入一个元素"在链表里是 $O(1)$，在数组里是 $O(n)$。选择数据结构，就是在选择你的操作代价结构。
四种基础结构
数组（Array）
内存中连续存储的相同类型元素序列。
内存地址：1000 1004 1008 1012 1016
元素： [10] [25] [7] [43] [18]
```核心特性： - 随机访问：$O(1)$（知道地址，直接跳转） - 末尾追加：$O(1)$（均摊） - 中间插入/删除：$O(n)$（需要移动后续所有元素） - 空间：连续，对 CPU 缓存极其友好
数组是最基础的结构，也是其他结构的构建材料。
"对缓存友好"值得展开一层：CPU 从内存取数不是一个字节一个字节地搬，而是以缓存行（cache line，主流 x86 上是 64 字节）为单位整块搬运。读一个 4 字节的整数，实际捎带回了它旁边的 15 个整数。数组元素恰好紧挨着排，遍历它们时几乎每一次缓存搬运都不浪费——这就是为什么同样是 $O(n)$ 的遍历，数组的常数因子远小于链表。
链表（Linked List）
每个节点存储数据和指向下一个节点的指针，节点在内存中不连续：
[10 | ->] ---> [25 | ->] ---> [7 | ->] ---> [43 | NULL]
```核心特性： - 随机访问：$O(n)$（必须从头顺序遍历） - 任意位置插入/删除：$O(1)$（只改指针） - 空间：碎片化，对缓存不友好，每个节点有额外指针开销
链表的价值在于动态性——大小完全灵活，插入删除不移动数据。
破除误解：链表"插入是 $O(1)$"常被误读。只改指针确实是 $O(1)$，但前提是你已经握着那个位置的节点指针。如果你只知道"在第 k 个元素后面插入"，得先从头走 k 步找到它，这一步仍是 $O(n)$。所以链表真正占便宜的场景，是在遍历过程中顺手删除或插入当前节点，而不是按下标随机插入。
还有一个现代硬件带来的反直觉结论：即便理论复杂度相同，链表在真实机器上常常慢于数组。原因是缓存局部性（cache locality）——数组元素紧挨着排在内存里，CPU 的预取器（prefetcher）能提前把后续数据装进缓存；链表节点散落在堆的各处，每跳一次指针都可能触发一次 cache miss。Bjarne Stroustrup 用一个经典基准测试说明这点：顺序遍历 std::list 可能比遍历 std::vector 慢上百倍。"理论最优"的链表，在很多场景里就这样输给了"理论更差"的数组。
树（Tree）
分层的非线性结构：
[8]
/ \
[3] [10]
/ \ \
[1] [6] [14]
```二叉搜索树（BST）满足：左子树所有节点 < 根 < 右子树所有节点。在此性质下，查找、插入、删除均为 （平衡时）。
树家族包括： - 二叉搜索树：有序字典操作 - AVL 树 / 红黑树：自平衡 BST，保证 最坏情况（Java 的 TreeMap、Linux 内核调度器使用红黑树）。AVL 树由苏联学者 Adelson-Velsky 与 Landis 在 1962 年提出，是历史上第一种自平衡二叉搜索树；红黑树则由 Guibas 与 Sedgewick 在 1978 年的论文《A Dichromatic Framework for Balanced Trees》中定型，它放松了平衡约束，换取更快的插入与删除。 - 堆（Heap）：父节点总大于（或小于）子节点，支持 插入和 取最值。它其实是"伪装成树的数组"——节点按层序塞进数组，下标为 i 的节点，父节点在 $(i-1)/2$，两个孩子在 $2i+1$ 和 $2i+2$，不需要存任何指针。优先队列、定时器调度、Top-K 问题的内核都是它 - Trie（前缀树）：字符串字典，自动补全的内核数据结构。"trie" 这个词由 Edward Fredkin 在 1960 年取自 retrieval（检索）的中间音节。 - B-Tree / B+ Tree：数据库索引的基础，为磁盘访问模式优化
B-Tree 值得单独说一句，因为它是"数据结构必须为硬件而设计"的范例。它由 Rudolf Bayer 与 Edward McCreight 在波音研究实验室提出，论文《Organization and Maintenance of Large Ordered Indices》1970 年 7 月首次流传、1972 年正式发表于《Acta Informatica》。
他们的出发点是：索引大到只有一小块能放进内存，其余必须留在磁盘上。磁盘一次寻道的代价是内存访问的成千上万倍，所以 B-Tree 让每个节点都"很胖"——一个节点容纳成百上千个键，恰好对应磁盘上的一页。这样树高极矮，查一条记录只需几次磁盘 I/O。今天 MySQL 的 InnoDB、PostgreSQL 的默认索引用的都是 B+ Tree，正是这套五十多年前的设计。
算一笔具体的账。数据库页的大小按系统而定：PostgreSQL 默认 8KB，InnoDB 默认 16KB，SQLite 自 3.12.0（2016 年）起默认 4KB。一个 16KB 的内部节点存 8 字节的键加 6 字节的指针，扇出可达上千。按保守的扇出 1000 估算：一层装 1000 个键，两层覆盖 100 万条记录，三层覆盖 10 亿条。而根节点和上层节点几乎总被缓存在内存里，于是 10 亿行的表里做一次点查，往往只需要一次磁盘 I/O。作为对照，若用二叉搜索树， 层就是最坏 30 次随机寻道，机械磁盘上就是约 0.3 秒——一次查询的差别就是"毫秒"与"秒"的差别。
B+ Tree 相对 B-Tree 的两处改进也都服务于磁盘：内部节点只存"路标"不存数据，同样一页能塞下更多键、扇出更高；叶子节点按键序连成链表，范围查询找到起点后顺着链表顺序读即可。这套结构的完整工程现场（页面布局、分裂与合并、崩溃恢复）见 SQLite 内核剖析；它与写优化路线 LSM 树的正面比较，见 B 树与 LSM 树。
跳表（Skip List）：用抛硬币代替旋转
平衡树能保证 ，代价是插入删除后要执行一套精细的旋转规则来恢复平衡——红黑树的实现以难写著称。1990 年，William Pugh 提出了一个出人意料的替代方案：不维持严格平衡，改用随机化。
跳表从一条普通的有序链表出发，然后给一部分节点"加层"：插入新节点时抛一枚不均匀的硬币，正面就升一层，再正面就再升一层，直到出反面为止（Redis 的实现里每次升级的概率是 1/4）。结果是每个节点期望只在 1/4 的上层出现，层层稀疏上去，期望总高度 。
第 3 层: 1 --------------------> 43
第 2 层: 1 --------> 17 -------> 43
第 1 层: 1 --> 7 --> 17 --> 29-> 43
第 0 层: 1->4->7->12->17->25->29->35->43
```查找从最高层出发：往右走，发现下一步会越过目标就往下降一层，像"高速转快速再转街道"的层级路网。查找、插入、删除的期望代价都是 ，全程没有一次旋转，核心实现百行以内。随机的代价是： 只是期望而非最坏保证——但退化的概率随规模指数下降，工程上可以当作不存在。
这套"够用且简单"的账，真实系统算得很清楚。Redis 的有序集合（Sorted Set）在数据量超过阈值时用跳表；作者 antirez 解释过选型理由：内存开销可通过升级概率调节，ZRANGE 这类范围遍历顺着底层链表走、缓存局部性不输平衡树，而实现和调试都简单得多。Google 的 LevelDB（2011 年开源）也把内存中的有序表（MemTable）建成跳表。Pugh 的原始论文发表在《Communications of the ACM》33 卷 6 期，标题就叫"跳表：平衡树的概率替代品"。
哈希表（Hash Table）
把键映射到数组位置：
key = "Alice"
hash("Alice") % table_size = 3
table[3] = {name: "Alice", age: 28}
```核心特性： - 查找、插入、删除：均摊 $O(1)$ - 无序（键之间没有顺序关系） - 代价：需要好的哈希函数；哈希碰撞需要处理；空间利用率有上限
哈希表是现代编程中最常用的数据结构之一，几乎所有高级语言都内置它（Python 的 dict，Java 的 HashMap）。
哈希的思想可以追溯到 1953 年 1 月，IBM 的 Hans Peter Luhn 在一份内部备忘录里提出：把数据丢进若干"桶（bucket）"，用一个由键算出的索引直接定位到桶，从而加速检索。这份备忘录同时也是已知最早提到链表的文献之一。
哈希表绕不开的核心问题是碰撞：两个不同的键算出同一个位置。两大解决流派各有取舍。链地址法（separate chaining）在每个桶挂一条链表，装填因子（load factor）可以接近甚至超过 1，删除也简单，代价是链表的缓存不友好。开放寻址法（open addressing）则在碰撞时探测表内的下一个空位，数据都留在连续数组里、对缓存友好，但通常装填因子超过 0.5 就得扩容重散列，删除也更麻烦。
这又是一个没有标准答案的权衡：Java 的 HashMap 走链地址法，而 CPython 的 dict 走开放寻址。
摊还分析：为什么"末尾追加"敢说 $O(1)$
前面说数组末尾追加是"$O(1)$ 均摊"，这个"均摊"值得展开，因为它是理解动态数组（Python 的 list、Java 的 ArrayList、C++ 的 vector）的关键。
数组容量是固定的，装满后再追加就得申请一块更大的内存、把旧元素整体搬过去——这一次搬迁是 $O(n)$。如果每次只多要一格，那么连续追加 n 个元素的总搬迁成本会累积到 ，慢得不可接受。
工程上的做法是容量翻倍：满了就扩到两倍。这样搬迁很少发生，n 次追加的总搬迁成本是 ，即 $O(n)$；平摊到每一次追加，就是 $O(1)$。注意这是"平均到每次操作"的均摊 $O(1)$，不是"每次都 $O(1)$"——某一次具体的追加仍可能触发一次昂贵的 $O(n)$ 搬迁。
这种"把偶尔的昂贵操作摊到大量廉价操作上"的分析方法叫摊还分析（amortized analysis），由 Robert Tarjan 在 1985 年的论文《Amortized Computational Complexity》中系统化，他提出的"势能法（potential method）"至今是分析这类自调整数据结构的标准工具。
图：关系的数学语言
图由节点（vertices）和边（edges）组成，是表达任意关系的最通用数据结构：
A --- B
| \ |
C D--E
```图的两种主要存储方式： - 邻接矩阵： 布尔矩阵，$M[i][j] = 1$ 表示 i 和 j 相连。空间 ，适合稠密图。 - 邻接表：每个节点存一个邻居列表。空间 $O(n + m)$（$m$ 为边数），适合稀疏图。
图能表达：社交网络中的朋友关系、城市间的道路网、网页之间的超链接、程序中的函数调用关系。谷歌的 PageRank 算法在图上运行；GPS 导航最短路径在图上计算。
栈与队列：限制访问的结构
栈（Stack）：后进先出（LIFO） - 只能在栈顶压入（push）和弹出（pop） - 用途：函数调用栈、撤销（undo）功能、括号匹配
队列（Queue）：先进先出（FIFO） - 只能在队尾加入、队头取出 - 用途：BFS 遍历、任务调度、消息队列
它们不是新的内存结构，而是对数组或链表加上访问规则限制——这本身就是一种抽象：对外只暴露必要的操作。
代价与争议：没有最好的结构
数据结构选择没有万能答案，只有针对具体场景的权衡：
| 操作 | 数组 | 链表 | BST | 哈希表 |
|---|---|---|---|---|
| 随机访问 | $O(1)$ | $O(n)$ | $O(1)$ | |
| 插入（头部） | $O(n)$ | $O(1)$ | $O(1)$ | |
| 删除 | $O(n)$ | $O(1)$ | $O(1)$ | |
| 有序遍历 | $O(n)$ | $O(n)$ | $O(n)$ | 不支持 |
| 范围查询 | $O(n)$ | $O(n)$ | 不支持 |
一个现实的案例：Redis 内部对小型哈希、小型列表并不用链式哈希或链表，而是用一块连续内存紧凑排布的编码——数据量小时，缓存友好性带来的收益远超链式结构的理论优势。早期的实现叫 ziplist，每个条目要记录前一个条目的长度以便反向遍历，于是一个条目变长可能引发后续条目长度的连锁重写（cascade update），最坏 ；2022 年发布的 Redis 7.0 把它整体换成了 listpack，改为在每个条目尾部记录自己的长度，连锁更新从结构上消失。"理论最优"不等于"实际最快"，而"实际最快"的设计自己也在被工程细节持续修正。Redis 把这些编码选择与单线程事件循环配合的完整逻辑，见 Redis 单线程模型。
另一个没有标准答案的选型：B+ 树与 LSM 树。B+ 树原地更新、读路径短，读多写少的场景占优，InnoDB 与 PostgreSQL 都选它；LSM 树把随机写转成顺序追加、后台合并，写吞吐高，Cassandra 与 RocksDB 走这条路线。两者的完整对比见 B 树与 LSM 树——选哪边，取决于你的负载里读和写的比例，而不是教科书里的渐近复杂度。
跨域连接
- 抽象与分层：栈和队列不是新的内存布局，只是在数组或链表之上加了访问规则。这恰好说明定义一个结构的不是"怎么存"，而是"哪些操作以什么代价可行"——对外只暴露必要操作，内部表示换掉也不影响调用者。推论是：换实现之前，先问清楚哪些操作的代价已经被调用方依赖了。
- 拉格朗日与哈密顿力学：摊还分析的势能法与力学记账同构：给结构定义一个非负的"势"，把每次操作的摊还代价写成实际代价加势差，昂贵的扩容由此前积累的势支付。只要初势为零，摊还之和就是实际总代价的上界。推论是：单次操作仍可能很贵，摊还保证的是总量而不是每一次。
- 概率论：跳表用随机层数替代严格平衡，期望高度是对数级，最坏情形仍可能退化，但退化概率随规模指数下降。这是一次典型交易——用概率保证换实现简单，代价是失去了确定性的最坏界。
- 形态学：前缀树把共享的词头合并成一条路径，正是词典按词干组织的做法。可检验推论：在后缀高度规则的语言里前缀共享率低、后缀共享率高，索引就该反向建树——结构由词法形态决定，而不由语言"难不难"决定。换句话说，索引结构该由数据的形态决定，而不由算法教材的章节顺序决定。
- 社会网络分析：现实网络稀疏且度分布极不均，因此邻接表比邻接矩阵省几个数量级空间。更要紧的是，遍历成本由少数枢纽节点决定而非平均度，最坏情形分析必须盯住这些节点，用平均值估算会严重低估。同理，稠密矩阵只有在小图、或需要做代数运算时才真正划算。
参考文献
- Sedgewick, R. & Wayne, K. Algorithms. 4th ed. Addison-Wesley, 2011.
- Goodrich, M. & Tamassia, R. Data Structures and Algorithms in Python. Wiley, 2013.
- Bayer, R. & McCreight, E. "Organization and Maintenance of Large Ordered Indices." Acta Informatica 1(3), 1972.（B-Tree 原始论文）
- Pugh, W. "Skip Lists: A Probabilistic Alternative to Balanced Trees." Communications of the ACM 33(6), 1990.（跳表原始论文）
- Tarjan, R. E. "Amortized Computational Complexity." SIAM Journal on Algebraic and Discrete Methods 6(2), 1985.（摊还分析与势能法）
- Guibas, L. J. & Sedgewick, R. "A Dichromatic Framework for Balanced Trees." Proc. 19th Annual Symposium on Foundations of Computer Science (FOCS), 1978.（红黑树原始论文）
延伸阅读
- Cormen, T. et al. Introduction to Algorithms (CLRS). 3rd ed. MIT Press, 2009. （数据结构与算法的权威教材）