个人学习站

深色模式

00 · 数据结构导读：数据怎么摆，决定了它有多快 ​

数据结构不是"八种容器的名字"，而是**"用空间换时间"的各种具体交易**。看懂这句话，这一模块就不用背了。

一句话本质 ​

所有数据结构都在做同一件事：用额外的空间或额外的约束，换取某种操作更快。

  • 数组：浪费"插入要挪动"的代价，换取"按下标随机访问 O(1)"
  • 哈希表：浪费空间（装不满），换取"查找 O(1)"
  • 树：浪费指针，换取"有序 + 查找 O(log n)"
  • 堆：只维护"局部有序"，换取"取最值 O(1)"

没有免费的午餐，只有不同的交易。选结构 = 选你要优化哪个操作、愿意付什么代价。

生活类比：找东西的不同方式 ​

结构场景
数组电影院的连排座位。知道排号就能直接坐下（O(1)），但中间要插一个人，后面全得挪
链表寻宝游戏：每张纸条写着下一张在哪。插入方便，但要找第 10 张必须从第 1 张开始
栈一摞盘子。只能从最上面拿、往最上面放
队列排队买奶茶。先来的先走
哈希表超市存包柜。按号码直接开柜，不用一个个找
二叉搜索树公司组织架构。找一个人，从 CEO 开始"大了往左、小了往右"
堆急诊分诊。不要求全员有序，只要求"最严重的那个永远在最前面"
图地铁线路图。站点之间有关系，找最短路径

模块地图：5 篇怎么接 ​

01 复杂度 —— 怎么衡量"快"（全模块的度量尺）
   |
   +-- 02 线性结构：数组 / 链表 / 栈 / 队列 / 哈希表
   |      优化"按下标访问"或"插入删除"
   |
   +-- 03 树与堆：二叉树 / 平衡树 / 堆
   |      优化"有序查找"和"取最值"
   |
   +-- 04 图与并查集：最短路 / 拓扑排序 / 连通性
   |      处理"多对多关系"
   |
   +-- 05 排序与二分：把前面所有结构用起来
          排序是"预处理"，二分是"利用有序"

关键连接：

  • 01 是尺子。后面所有"这个结构更快"的结论，都要用 01 的语言（O(n)、O(log n)）表述。
  • 02 的哈希表 和 03 的树 是"查找"的两种方案：哈希 O(1) 但无序，树 O(log n) 但有序。这个对比直接决定了数据库索引为什么用树不用哈希。
  • 03 的树 是 04 数据库 B+ 树的前置。不先懂二叉树和平衡树，B+ 树就是死记硬背。
  • 05 的排序 是所有算法的"预处理步骤"，而二分是"利用有序"的极致。

一条主线：为什么数据库用 B+ 树而不用哈希 ​

这条线把整个模块串起来，建议先看一遍：

问题：1000 万行数据，怎么快速找到某一行？

方案 1：数组 + 线性扫描
  > O(n)，1000 万次比较，太慢

方案 2：哈希表
  > 查找 O(1)，很快
  > 但：① 不支持范围查询（age > 20 得全扫）
        ② 不支持排序（ORDER BY 用不上）
        ③ 哈希冲突退化，且扩容代价大
  > 结论：等值查询可以，范围查询不行

方案 3：二叉搜索树
  > 查找 O(log n)，且天然有序
  > 但：① 退化成链表时是 O(n)（所以要平衡树）
        ② 每个节点只存一个值 > 树高 log2(1000万) ≈ 24 层
        ③ 每层一次磁盘 IO > 24 次 IO，太慢

方案 4：B 树（多叉）
  > 每个节点存几百个值 > 树高降到 3~4 层
  > 磁盘 IO 从 24 次降到 3~4 次

方案 5：B+ 树（B 树的改良）
  > 数据只在叶子节点，非叶子只存索引 > 一个节点能装更多键 > 树高更低
  > 叶子节点用链表串起来 > 范围查询直接顺序扫，不用回到根
  > 结论：这是数据库的最终选择

看懂这条线，你就同时懂了：数组、哈希、二叉树、平衡树、B 树、B+ 树，以及它们各自的取舍。这比背六段定义有用得多。

学习这个模块的方法 ​

  1. 每个结构都问三个问题：它优化了哪个操作？代价是什么？什么场景下会退化？
  2. 一定要手写。二分和快排的边界，不手写三遍永远记不住。
  3. 不要背代码，背"为什么这么写"。比如二分为什么用 left + (right-left)/2（防溢出），为什么循环条件是 left <= right（闭区间）。
  4. 复杂度要能"看出来"，不是背出来的。看到"每次砍一半"就是 log n，看到"嵌套两层"就是 n²。

和其他模块的连接 ​

  • < 来自 虚拟内存：让每个程序都以为自己独占一台机器：数组快于链表的根本原因是缓存局部性，属于内存布局问题
  • > 影响 索引与 B+ 树：B+ 树是这里树结构的直接应用，一个节点 = 一个磁盘页（16KB）
  • > 影响 事务与 ACID：undo log 是链表、redo log 是环形数组，都是这里的基础结构
  • > 影响 工程实践：Redis 的跳表（有序链表 + 多级索引）、Java 的 HashMap（数组 + 链表 + 红黑树）、Kafka 的稀疏索引

自测 3 问 ​

Q1：为什么说"所有数据结构都是空间换时间"？这个说法有反例吗？

点开看答案

大体成立，但不绝对。更准确的说法是"用一种操作的代价，换另一种操作的效率"。

  • 哈希表：确实是用空间（装不满的桶）换查找时间。
  • 链表：反而是用时间换空间（插入快，但查找慢，且每个节点多一个指针的空间开销）。
  • 数组：用"插入慢"换"随机访问快"，空间上还更省（没有指针）。
  • 堆：用"整体无序"换"取最值快"。

所以真正的统一表述是：没有一种结构在所有操作上都最优，选结构就是选"哪个操作最重要"。面试时这样答，比背"空间换时间"更显得懂。

Q2：既然哈希表查找 O(1)，为什么不用它做数据库索引？

点开看答案

三个致命问题：

  1. 不支持范围查询。WHERE age > 20 用哈希只能全表扫，因为哈希把相邻的值打散了。B+ 树叶子有序且相连，范围查询直接顺序扫。
  2. 不支持排序。ORDER BY 用不上哈希索引，只能额外排序。
  3. 最左前缀失效。联合索引 (a,b)，只查 b 时哈希完全用不了；B+ 树可以利用前缀。

哈希索引确实存在（MySQL 的 MEMORY 引擎、InnoDB 的自适应哈希索引），但只用于等值查询的加速，是补充而不是主力。

Q3：为什么平衡树能保证 O(log n)，普通二叉搜索树不能？

点开看答案

因为普通 BST 的形态取决于插入顺序。

按 1,2,3,4,5 顺序插入，树会退化成一条链（每个节点只有右孩子），查找变成 O(n)——和链表没区别。

平衡树（AVL、红黑树）通过旋转维持"左右子树高度差不超过常数"，强制树高保持在 O(log n)，所以最坏情况也是 O(log n)。

代价：每次插入/删除可能触发旋转，常数开销变大，实现也复杂得多。这就是"用一点性能换最坏情况的保证"。

类比失效处 / 易错点 ​

  • "电影院座位"类比会让人以为数组插入一定慢。在尾部追加是 O(1)（摊销），只有在中间插入才要挪动。
  • "哈希 O(1)"是平均情况。最坏情况（全部冲突）是 O(n)，Java 8 之后冲突多了会转红黑树变成 O(log n)。
  • "树都是 O(log n)"不成立。只有平衡的树才是；普通 BST 最坏 O(n)。
  • 复杂度忽略常数，但工程里常数很重要。O(log n) 的树在 n 很小时，可能比 O(n) 的数组还慢（缓存不友好 + 指针跳转）。
  • "堆是有序的"是错的。堆只保证"根是最值"，其他位置无序。所以堆不能做范围查询，也不能中序遍历出有序序列。

✅ 验收清单 ​

  • 能用一句话说清"选数据结构本质是在权衡什么"，并举出数组/链表/哈希/堆各自优化了哪个操作
  • 能画出模块地图，说出 5 篇之间的依赖关系（尤其"树 > B+ 树"这条）
  • 能完整讲出"为什么数据库用 B+ 树"那条主线（从数组 > 哈希 > BST > B 树 > B+ 树）
  • 能说出哈希表不适合做数据库索引的三个原因
  • 能解释"普通 BST 会退化成链表，平衡树怎么避免"
  • 合上书，用自己的话讲 3 分钟，中途不卡壳