历史地图：数据结构与算法是怎样演进的

我最开始刷算法题的时候，总觉得数组、红黑树、B + 树这些名词是教科书为了面试凭空造出来的。后来翻看演进历史才恍然大悟：没有哪个数据结构是为了考试而生，它们全部来自人类真实遇到的计算痛点。

数据结构与算法不是一套面试题库，它来自人类处理计算、检索、排序、通信、资源分配的漫长过程。读懂这条历史主线，后面遇到的名词就不会感觉是凭空出现的陌生概念。

这篇不需要记忆具体年份，核心抓住这条逻辑：当计算工具、存储介质、数据规模发生变化，人们就会发明出新的数据表示方法与计算步骤。

图：算法早于电子计算机，现代数据结构则与内存、磁盘、网络和大规模数据共同演进

算法比计算机古老得多

“算法” 这个词源自九世纪的波斯学者花剌子密，但按固定步骤解决问题的思想要更早。 比如古希腊的欧几里得算法（辗转相除法），用反复取余的方式求最大公约数，两千多年后的今天，Java 工具类（java.math.BigInteger 可以在这里面看一下gcd）里还能看到它的身影。

早期的算法就已经具备这几个核心特征：

• 输入明确
• 步骤有限、可以手动执行
• 合法输入一定能得到确定结果
• 同一套规则可以反复复用

所以要记住：算法本质是一套描述解题过程的精确步骤，它不等于某门语言的代码，没有计算机也可以存在。

从人工计算到机械制表

商业统计、人口普查带来了海量排序、汇总的需求，穿孔卡片和机械制表设备登场，“数据该怎么排列存储” 第一次变成实打实的效率问题：按列排序、按编号查找、记录分组，这些需求和今天后端做的数据处理几乎一脉相承。

这个时代的存储介质读写成本很高，所以诞生了一条延续至今的工程思想：尽量规避昂贵的随机访问，优先做批量、顺序处理。 我们现在学的外部排序、MySQL 数据库页、B + 树，底层都还在沿用这套思路。

电子计算机让内存结构成为核心问题

电子计算机出现后，我们需要在有限的内存空间里存放指令与数据： 连续的内存空间，演化出数组； 用地址把分散节点串起来，演化出链表； 限制访问顺序，演化出栈、队列； 用键直接定位数据，演化出哈希表。

这些结构不是纸上的概念，它们直接沉淀到编程语言标准库里：Java 的ArrayList底层是数组，LinkedList底层是双向链表，HashMap底层是哈希表。

二十世纪五十年代，链表被用在早期 AI 符号计算，栈用来模拟函数调用、回溯；哈希表把 “逐条遍历查找” 升级成 “按键直接定位”，直到现在还是工程里最高频的结构。

为什么会出现平衡树

普通二叉搜索树BST在理想情况下查找速度很快，但如果按照有序序列插入，就会直接退化成链表，查询效率直接从O(logn)掉到O(n)。1962 年发表的 AVL 通过严格的高度平衡，解决了BST退化的最坏情况。

之后随着磁盘存储的普及，又诞生了多路搜索树。B 树由 Rudolf Bayer 与 Edward McCreight 在 1970 年前后提出，它让单个节点可以存放多个键，以此减少磁盘IO次数。我们熟悉的红黑树和对称二叉 B 树其实思想同源，也就是Java TreeMap的底层实现。而B+树就是MySql索引的核心。

这段演进告诉我们一个非常重要的结论：不存在脱离硬件、业务场景的“完美数据结构”。

AVL 树平衡严格，但更新开销大；红黑树在查询性能和更新成本之间做了折中；B + 树专门针对磁盘页和范围扫描做优化。选型永远要看你的场景。

图算法来自道路、网络与调度问题

欧拉的柯尼斯堡七桥问题，是图论的经典起点。 图的威力在于抽象能力：把现实事物抽象成点，事物之间的关系抽象成边，道路规划、通信链路、任务依赖、社交好友关系，都能用同一套模型描述。

中期一批经典算法陆续成型：

• Dijkstra：解决非负权图的单源最短路径
• Prim、Kruskal：解决最小生成树，做低成本连通
• Ford–Fulkerson：最大流与增广路框架
• Tarjan：线性时间求解强连通分量

学习图算法的忠告：先想现实问题怎么建模成图，再去选算法，不要上来就死背模板。 后端开发里的服务依赖调度、链路追踪、社交关系链，本质都是图的建模。

动态规划、字符串与信息检索

Bellman 在 50 年代提出动态规划，很多人误以为 DP 是 “填表的小技巧”，但它的核心思想是复用已经算过的子问题结果，避免重复计算，用来处理多阶段的决策问题。

文本数据爆发之后，字符串匹配和信息检索变成刚需： KMP、Aho‑Corasick、Manacher 分别解决单模式匹配、多模式匹配、回文串问题； 倒排索引把 “文档包含哪些词” 反转成 “词出现在哪些文档”，是 Elasticsearch 这类搜索引擎的基石。

概率型结构与分布式时代

当数据规模膨胀到，我们没办法给每一条数据都保存完整信息的时候，人们开始接受可控误差，来换取巨大的空间、时间收益。

1970 年提出的布隆过滤器（Bloom Filter）就是典型，Java 的 Guava 库就提供了它的实现，用很小的内存做元素存在性判断，允许出现误判。

分布式系统又抛出了新的问题：缓存淘汰、节点扩容缩容、海量数据估算去重。 LRU（Java 可以用LinkedHashMap实现）、跳表、一致性哈希、各类概率结构，本质都是在时间开销、空间开销、结果准确性、系统复杂度之间做取舍。

一条更容易理解的学习顺序

历史不是为了增加背诵负担，而是告诉我们：新的结构，是旧方案扛不住新约束才诞生的。所以学习可以顺着这条问题演进路线：

1. 先理解内存、数组、链表、栈和队列
2. 再理解快速定位与有序关系：哈希表、堆和搜索树
3. 然后处理复杂关系：并查集、图与图算法
4. 再学习通用算法思想：分治、搜索、贪心、动态规划
5. 最后进入磁盘、海量数据和分布式场景

记住一句话：每一种新结构都不是炫技，抓住旧方法的痛点在哪里，你就理解了它的来历。

自测问题

读完可以试着用自己的话回答，检验理解：

1. 为什么算法的历史早于电子计算机？
2. 为什么磁盘的硬件场景，推动了多路搜索树（B/B + 树）的发展？
3. AVL 树试图修复普通二叉搜索树的什么缺陷？
4. 图结构为什么可以统一描述道路、任务依赖、社交好友这完全不一样的现实关系？
5. 概率型结构为什么愿意接受可控的误差？