全书最后一章，视角陡然拉远：前面 13 章我们都假装内存无限大、访问不要钱。现实是：磁盘比内存慢 10 万倍以上。这一章讲两件事——内存怎么管理，以及数据装不下内存时怎么办 💾。
🧠 内存：一条长长的地址走廊
把内存想象成编号的房间走廊：每个房间 4~8 字节，房间号就是地址。程序里所有东西最终都住在这些房间里。
C++ 内存分三个区：
- 静态区：全局变量，程序出生就有， lifetime 伴随始终；
- 栈区：局部变量、函数调用信息，自动分配自动回收——但大小有限（通常几 MB），递归太深就「爆栈」💥；
- 堆区（heap）：
new申请、delete释放，大小可控、生死由你——也正因如此，事故高发 ⚠️。
🕳️ new/delete 背后：自由链表
每次 new 都找操作系统要内存？太慢了。运行库的做法：预先向系统批发一大块，零售给 new。零售的账本就是自由链表（freelist）：
new：从自由链表摘一个大小合适的块；delete：块还回链表，而不是还给系统；- 邻居块空闲时合并（coalescing）成大块，防止越切越碎。
由此引出著名的内存碎片问题：
- 外部碎片：总空闲空间够大，但都是零散小块，要 1MB 时拿不出连续的 1MB——像口袋里有 50 块硬币却付不了 50 元整钞 😫；
- 内部碎片：块按 2 的幂分配（8/16/32...），要 17 字节只能给 32，浪费近一半。
应对手段：紧凑化（compaction）——把所有存活对象搬家挤到一起，腾出整块空间（需要句柄间接寻址）。现代语言（Java/Python）的垃圾回收器干的就是这件事，C++ 把控制权留给你，也把责任留给你 ⚖️。
💽 换个战场：磁盘的代价模型
数据大到内存装不下（数据库动辄几百 GB），每条指令都要走磁盘。关键数字对比：
| 介质 | 随机访问延迟 | 类比（放大 10 亿倍） |
|---|---|---|
| 内存 | ~100 ns | 从书桌拿纸，1 秒 |
| SSD | ~100 µs | 从书架取书，2 分钟 |
| 机械盘 | ~10 ms | 跑一趟别的城市，4 个月 🐌 |
结论：磁盘时代，决定性能的不是 CPU 步数，而是磁盘 I/O 次数。磁盘一次读一整块（block，通常 4~64KB），所以——让每个磁盘块携带更多信息、让树更矮。
🌲 B-Tree：为磁盘而生的矮胖树
二叉树存 1 亿条数据高度约 27 层——27 次磁盘随机读，每读一次「跑一趟别的城市」，直接起飞 ✈️💸。
B-Tree 的思路：把 BST 的每个节点膨胀成一个磁盘页，一页装几百个 key（m 阶 B 树：每节点 ≤ m-1 个 key，≥ ⌈m/2⌉ 个孩子，所有叶子同层）。一页 500 个 key 时，1 亿条数据高度只需 3~4 层——磁盘 I/O 从 27 次降到 4 次以内，这就是数量级的胜利 🏆。
机制要点：
- 查找：页内用二分定位，然后顺着孩子指针下潜——每次下潜 = 一次磁盘 I/O；
- 插入溢出：节点满员就分裂成两半，中间 key 上浮给父节点——树向上长，所有叶子永远同层；
- 删除欠员：向兄弟「借」或和兄弟合并，维持 ⌈m/2⌉ 的下限；
- 变体 B+ 树：数据全在叶子层且叶子串成链表——范围查询（BETWEEN、ORDER BY）沿链表扫就行。MySQL InnoDB 的索引就是 B+ 树，这一节直接解释了你每天用的数据库 🗄️。
🎓 全书终章：三句话带走
- 数据结构 = 为特定访问模式定制的组织方式——先想清楚「将来怎么查、怎么改」，再选结构；
- 一切权衡皆有代价——快慢、空间、简单性、缓存友好，工程师的功力体现在「知道自己在放弃什么」；
- 存储介质的物理特性决定抽象设计——内存有 RAM 模型，磁盘有 B-Tree，未来的存储介质还会催生新的结构。
14 章通关 🎉。接下来最好的学习方式：打开 IDE，把每章的数据结构亲手实现一遍——纸上得来终觉浅，绝知此事要躬行 💪。