玻尔百科数据结构是高效软件的基石，然而，在教学中，它们常被当作一个需要记忆的静态容器目录。这种观点忽略了该领域的精髓：数据结构设计是一种动态且富有创造性的工程行为。它是抽象算法需求与计算机具体物理约束之间的一场对话。了解数组或链表是什么，与了解为什么你可能会为数据库选择列式布局或为人工智能选择持久化树，这两者之间的差距，就在于理解这场对话。
本文深入探讨数据结构设计的艺术与科学，超越简单的工具清单，探索指导专家实践的基础原则。你将发现，关于内存布局、时间权衡和硬件交互的微妙选择，如何能导致性能上的巨大差异。第一部分，原理与机制，将揭示影响设计的基本计算物理学，从空间局部性和缓存到现代存储的特殊规则。随后，关于应用与跨学科联系的部分将展示如何将这些原则编织在一起，为金融、科学计算、人工智能等领域的复杂问题构建优雅而强大的解决方案。
在我们理解数据结构设计的旅程中，我们现在从“是什么”转向“为什么”和“怎么样”。数据结构不仅仅是信息的容器；它是一台精心打造的机器，一种策略的体现。它的设计是算法的抽象逻辑与运行它的计算机所遵循的刚性物理定律之间的一场对话。要做好设计，就要理解这场对话的本质。我们将探讨支配这门艺术的核心原则，看一看简单的权衡如何能导致截然不同的结果。
想象你有一个藏有一千本书的图书馆，你需要回答一个非常具体的问题：“每一本书第三章的第一句话是什么？”你可以拿起第一本书，读到第三章，记下那句话，然后换到第二本书，依此类推。这很费力。你大部分时间都花在翻阅你不在乎的书页上，只为了找到你需要的那一点信息。
现在，想象一位神奇的图书管理员为你准备了一个特殊的活页夹。这个活页夹里只包含了每本书第三章的第一句话，全部一句接一句地列在一张长长的卷轴上。你的任务变得轻而易举。你只需沿着卷轴往下读就行了。
这个简单的类比捕捉了数据结构设计中最基本的选择之一：内存布局。当计算机程序需要访问数据时，读取一个连续的内存块远比跳转到几十个不同位置要快得多。这个原则被称为空间局部性。CPU就像一个热切的读者，拥有一张小书桌（即缓存）。一次性把一整叠相关文件拿到桌上，远比为每张单独的文件都跑回书架要高效得多。
思考一下在内存中表示数据库查询结果的挑战。结果是一张有行有列的表。一个自然的想法是按行组织数据，就像它在屏幕上显示的那样。这被称为结构体数组（AoS），或行式存储。每一行都是一个整洁的包，包含其所有字段（例如，ID、名称、日期）。如果你需要显示一整行，这很棒。但如果你是一位分析师，试图计算数百万行中某一列（比如“销售价格”）的平均值呢？行式存储方法迫使计算机遍历每一行的所有数据——ID、名称、日期——只为了挑出那一个数字。这是极其浪费的，就像把每本书从头到尾读一遍一样。
另一种方法是那位神奇图书管理员的方法：数组结构体（SoA），或列式存储。在这里，“ID”列的所有值都存储在一个连续的内存块中。“销售价格”的所有值在另一个块中，“日期”的所有值又在另一个块中。现在，要计算平均销售价格，计算机只需要读取一个内存块——一次简单、闪电般的扫描，就像沿着卷轴往下读。这种将每一列存储在同构数组中的设计，尊重了空间局部性，对于分析型查询来说效率极高。
这两种布局，AoS和SoA，只是相同数据的不同排列方式。事实上，通过一个巧妙的原地算法，人们可以将AoS布局转换为SoA布局，而无需使用任何显著的额外内存，只需根据将元素旧位置映射到新位置的置换环来仔细交换元素即可。它们之间的选择并非关乎对错，而是关乎理解你将要对数据提出什么样的问题。
每一项设计都涉及权衡，一个常见的权衡是在“现在完成的工作”和“以后完成的工作”之间。你是愿意花时间预先精心组织数据，还是每次需要时再去处理混乱？答案完全取决于你预期的工作负载。
想象两种字典设计。设计X构建起来需要很长时间，比如说与成正比，其中是条目数。但一旦建好，查找一个词是瞬时的，耗时。设计Y构建起来快得多，可能耗时与成正比，但每次查找都需要多做一点工作，比如说耗时。哪一个更好？
一个优美的数学事实是，对于任何固定的正常数和，像这样的多项式函数，当足够大时，其增长速度总是会超过像这样的多对数函数。这意味着设计X的预处理成本从根本上说比设计Y更昂贵。
所以，如果你只打算进行几次查找，设计Y更快的预处理使其成为明显的赢家。但如果你计划进行大量的查询，比如说次查询呢？在这种情况下，设计Y的总时间将被缓慢的查询所主导，总计约为。而设计X，尽管其构建成本巨大，却能轻松完成查询，其总时间保持在。对于这种工作负载，设计X更快！最佳设计并非绝对的，而是相对于你正在解决的问题而言。
到目前为止，我们的原则都还比较抽象。但数据结构并非抽象之物。它们是机器中比特的物理排列，而那台机器的物理特性至关重要。
我们已经提到了CPU缓存，但让我们看得更仔细些。CPU对已在其缓存中的数据执行计算所需的时间可能只有几个周期。但如果数据不在缓存中——即发生缓存未命中——从主存（DRAM）中获取数据所需的时间可能是几百个周期。CPU只能空闲等待。这就是我们必须对抗的“延迟”成本。
考虑合并个预排序数据列表的任务，这是对内存放不下的大文件进行排序时的常见步骤。一种标准方法是使用优先队列来跟踪这个列表中每一个的头部最小项。在每一步中，你提取出全局最小项，然后需要从它所属的列表中获取下一个项。问题是，这个列表的头部散布在内存各处。每次你推进一个列表的头部时，你很可能会跳转到一个新的、未被缓存的内存位置，从而招致那高达180个周期的巨大延迟惩罚。
你如何对抗这种情况？你可以作弊。你可以预见未来。现代CPU有一条名为“预取”的指令，它像一个不具约束力的提示：“嘿，我可能过一会儿就需要这个内存地址的数据了，所以你或许可以现在就开始取？”如果你时机把握得当，数据会在你需要它的时候正好到达缓存，延迟就完全被隐藏了。关键是计算“预取距离”——你需要提前多少个操作来发出预取指令。这是一个简单却意义深远的计算：你用内存延迟（例如，个周期）除以你的算法一步可以完成的计算量（例如，个周期）。结果告诉你需要提前多少步来隐藏等待时间。这是一个与硬件对话来设计算法的绝佳例子。
当我们处理像固态硬盘（SSD）中的NAND闪存这样的存储时，这场对话变得更加有趣。闪存有一个奇特的规则：你不能简单地覆盖一小块数据。要改变哪怕一个字节，你必须首先擦除一个非常大的内存块，这是一个缓慢且昂贵的操作，同时也会磨损设备。然而，向一个新鲜的、已擦除的页面写入是很快的。
这完全颠覆了传统的数据结构设计。像B+树这样的经典数据库索引，是为磁盘设计的，它假定可以原地更新其结构的小部分。在闪存上这样做会慢得灾难性。那么，我们该怎么办？我们改变游戏规则。我们采用写时复制（CoW）的策略。
你不是去修改一个数据块（一个“页面”），而是制作它的一个副本，将你的更改应用到副本上，并将这个新版本写入闪存驱动器上的一个新位置。然后，你更新父指针以指向这个新版本。旧版本仅被标记为“过时的”或“无效的”。这种只追加的方法将成本高昂的原地更新转化为一系列快速的写入。过时的页面最终由一个名为垃圾回收器的后台进程回收。这是一招漂亮的智力柔术：通过拥抱约束（无原地更新），我们得到了一个更健壮、性能更高的解决方案。像B-link树这样的技术甚至更为复杂，允许更新懒惰地向上传播到树中，进一步减少单次更改所需的写入次数。
写时复制的思想引导我们走向一个更普遍的原则：“原地”操作和“非原地”操作之间的区别。一个原地算法直接修改其输入。一个非原地算法则创建一个新的副本。
CoW策略免费为我们带来了一个强大的副作用。由于我们从不销毁数据的旧版本，如果我们愿意，我们可以将它们保留下来。这使我们能够创建持久化数据结构，它能记住其历史的每一个版本。
这方面的一个实际应用是创建一个“快照迭代器”。想象你有一个任务队列。你想生成一份队列中当前所有任务的报告，但在你生成报告时，程序的其他部分会继续添加和移除任务。如果你的报告生成器只是遍历实时队列，它会看到一个不断变化的列表，导致报告不一致且不正确。解决方案是创建一个快照。在你开始的那一刻，你对整个任务列表进行一次快速的、非原地的复制。然后你的报告生成器就在这个静态的、不变的副本上工作，与实时队列的混乱完全隔离。同样是这个原则，通常用更高效的写时复制机制实现，驱动着版本控制系统、你最喜欢的编辑器中的“撤销”功能，以及现代数据库的事务完整性[@problem_troll:3241106]。
但如果复制太慢了怎么办？哈希表是一种常见的数据结构，当它变得太满时，偶尔需要调整自身大小。标准方法是一个“全局暂停”事件：分配一个巨大的新表，然后费力地将旧表中的每一个元素复制到新表中。对于一个有数百万条目的表来说，这可能导致应用程序出现明显且不可接受的冻结。
对于像航空电子或高频交易这样的实时系统来说，这样的暂停不仅仅是恼人，它是一种致命的故障。解决方案是在复制上耍点小聪明。我们不是一次性完成所有复制，而是增量地进行。这种技术被称为去摊销（deamortization）。当触发调整大小时，我们分配新表，但保留旧表。然后，对于每一次后续操作（插入、查找），我们都做一点额外的工作：我们将几个元素从旧表移动到新表。这项额外工作的成本被严格限制在我们的延迟预算之内。随着时间的推移，旧表逐渐被清空，一旦为空，就可以被丢弃。我们把一个巨大的、不可预测的暂停，分解成了一系列微小的、可预测的、无害的步骤。
最后，有时候最重要的原则是最微妙的，是我们甚至不知道自己依赖的隐藏契约。考虑一下排序算法的稳定性属性。如果你按城市对一个人员列表进行排序，其中有多个人来自“纽约”，一个稳定的排序能保证他们在输出中保留其原始的相对顺序。一个不稳定的排序则不作此保证。
这重要吗？在某些情况下，它至关重要。想象一个优化编译器正在为处理器安排要执行的指令。它可能会为每条指令分配一个优先级——例如，内存操作获得高优先级，算术运算获得低优先级。然后它按此优先级对指令进行排序。但如果两条内存操作具有相同的优先级，会发生什么？假设原始代码是：
1 写入内存位置 A。2 写入同一内存位置 A。A中的最终值应该是2。但如果编译器使用不稳定的排序来安排这些指令，它可能会因为它们具有相同的优先级而交换它们的顺序。程序随后将首先执行第二次写入，然后执行第一次写入，在内存A中留下不正确的值1。这将是一个微妙、令人抓狂难以发现的错误。它的产生是因为违反了一个看不见的契约：程序员假设编译器的重排会尊重原始程序的逻辑，而编译器设计者则含蓄地依赖排序算法的稳定性来确保这一点。
这个教训是深刻的。设计健壮的系统不仅仅关乎布局和复杂度这样的大思想，也关乎欣赏那些细则、微妙的属性，以及支撑整个逻辑大厦的隐藏假设。数据结构设计之美就在于这种多层次的思考——从宏伟的架构蓝图到单个比特，所有这一切都与机器那不容置疑的物理定律进行着对话。
在我们遍历了数据结构的原理和机制之后，人们可能会倾向于将它们视为一个完整的工具目录，一套从教科书中背诵下来的已解决问题。但这就像看着一堆齿轮、杠杆和弹簧，却错过了钟表制作的艺术。真正的魔力不在于单个组件，而在于它们组合的艺术。数据结构的设计是一种创造性的工程行为，一个理解问题独特灵魂并打造出与之共鸣的结构的过程。
在本节中，我们将探索这一创造性过程。我们将看到基本思想如何被编织在一起，以解决横跨众多学科的复杂现实挑战——从互联网的底层管道和金融市场的狂热能量，到基因调控的精妙舞蹈和数学证明的抽象世界。我们将发现，“最好”的数据结构从来不是一个普适的答案，而是一个定制的解决方案，为数据、所需操作，乃至运行它的硅芯片的物理定律量身定做。
让我们从最简单的结构之一——链表开始。想象细胞中基因激活的级联反应，一个我们可以建模为简单节点列表的线性影响链，每个节点指向下一个。现在，如果一个抑制剂逆转了这个流程呢？在我们的模型中，这对应于反转链表。这个结构本身——一个由单向next指针构成的链条——定义了这个难题。我们不能直接跳到末尾然后从后往前开始。解决方案是一场优雅的三个指针之舞，迭代地遍历列表，反转每个链接，而从不失对链条的掌控。这种简单的指针操作，在没有额外内存的情况下原地完成，是数据结构设计的缩影：一个由结构本身的约束所决定并与之和谐共处的解决方案。现在，让我们看看这场设计之舞是如何在更宏大的舞台上上演的。
从本质上讲，数据结构设计往往是对速度的不懈追求。当你处理数十亿笔交易或模拟宇宙时，效率不是奢侈品；它是可能与不可能之间的界限。但这种速度并非通过蛮力实现。它是通过聪明才智、远见卓识以及对计算机实际工作的深刻尊重来实现的。
考虑这样一个场景：你需要管理许多不同的物品组，每组都有一个优先级，但你还需要对整个组应用一个更改——比如，降低优先级。一个朴素的方法是遍历组中的每一个物品并更新它。如果一个组有一百万个物品，那就是一百万次操作。如果经常这样做，你的系统就会陷入停顿。
这里的设计洞见是懒惰。为什么要现在做那些以后可能不需要的工作呢？我们可以不改变每一个物品，而是为整个组关联一个单独的“懒惰标签”或偏移量。这个偏移量代表了累积的总变化。一个物品的真实优先级现在是它存储的值减去这个组的偏移量。这样，一次批量更新就变成了一个单一的、常数时间的操作：只需更新偏移量！
当然，这又带来了新问题：当每个组都有自己的偏移量时，你如何找到所有这些组中的全局最小物品？解决方案是将简单的结构优美地组合成一个层次结构。我们可以为每个组维护一个独立的优先队列（比如一个二叉堆），存储物品未经调整的键。然后，我们使用一个单一的、全局的优先队列，它只保存每个组的顶部物品，但其键已由该组的懒惰偏移量调整过。当我们需要全局最小值时，我们只需查询这个顶层堆。当一个组的偏移量改变时，我们只需为其最小值在全局堆中添加一个新的、更新过的条目，知道旧的、“过时的”条目稍后会被忽略。这种两级结构巧妙地将堆的效率与懒惰求值的力量结合起来，将一个潜在的二次方问题转变为对数问题。这是一个通过组合现有结构来满足独特操作需求的经典例子。
有时，一个慢得无可救药的数据结构和一个快如闪电的数据结构之间的界限，就是一对听起来简单的规则。没有比不相交集联合（Disjoint-Set Union，DSU）数据结构更好的例子了，它用于跟踪元素到一个不相交集合的划分。它在图算法、网络连通性分析，甚至在约束满足问题中为变量等式建模方面都至关重要。
想象每个集合都是一棵树，根节点是集合的代表。要合并两个集合，你只需将一个根设为另一个的孩子。要查找一个元素属于哪个集合，你只需沿树向上走到根。很简单，对吧？但如果你不小心，你可能会创建出长而纤细的树，它们本质上就是链表。这样一次find操作就可能需要线性时间。
于是，两种设计原则登场了，通常被称为“启发式方法”：按秩合并和路径压缩。在合并两棵树时，按秩合并的原则是总是将较矮的树附加到较高树的根上，防止树不必要地加深。路径压缩的原则是，在你为一个元素找到根之后，你回头将该路径上的每个节点都直接设为根的孩子。这极大地扁平化了树。
这两个规则都不复杂，但它们共同产生的效果是惊人的。它们改变了结构，使树保持得极其浅。操作的时间复杂度从潜在的骤降到一个在所有实际应用中都接近常数的函数（，其中是反阿克曼函数，其增长速度如此之慢，对于任何可以想象的输入大小，它的值都小于5）。这不仅仅是一种改进，它是一种相变。一个简单、优雅的设计选择将数据结构从一个理论上的奇物，转变为算法设计中最强大、应用最广泛的工具之一。
性能不仅仅关乎抽象的操作计数；它还关乎计算机的物理现实。现代CPU快得令人难以置信，但它们渴望数据。瓶颈常常是從內存中獲取數據所需的時間。优秀的数据结构设计会考虑到这一点。
考虑评估分段多项式或样条曲线的任务，这在计算机图形学、科学模拟和数据分析中至关重要。样条由一系列在不同区间上的多项式“片段”定义。要对其求值，你首先要为你的查询点找到正确的区间，然后评估相应的多项式。
一个基于指针的树结构似乎很自然。但一个高性能的设计会做一些更简单、更深刻的事情。它将区间断点（节点）存储在一个简单的、连续的数组中。每个片段的多项式系数则存储在相应的二维数组中。为什么？因为这种布局对现代处理器来说简直是天籁之音。
为一批查询点找到正确的段，可以通过对节点数组进行向量化的二分查找来完成，这是一个高度优化且能最小化导致CPU停滞的不可预测分支的操作。一旦找到段，相应的系数就会被“收集”到一个块中。多项式求值本身使用霍纳法则，这是一种能最小化乘法次数的重构方法，并且可以一次性对一个点的向量执行。整个流水线——从搜索到求值——以最小的摩擦流经处理器，最大限度地利用其并行算术单元并高效地从内存中预取数据。在这里，获胜的设计不是一个复杂的指针网络，而是不起眼的数组，经过深思熟虑的安排，以便与硬件协同工作。
除了纯粹的速度，最优雅的设计是那些能反映问题本身结构的设计。数据结构成为一种表达问题逻辑、其规则及其自然划分的语言。
互联网骨干网中的一个核心交换机是数据处理的奇迹。它的工作是查看每一个数据包的目的地址，并决定下一步将其发送到哪里。这个决定，称为最长前缀匹配，必须在纳秒内完成。挑战因存在两种共存的协议而加剧：较旧的32位IPv4和较新的128位IPv6。
你如何为这个混合世界设计一个路由表？你是否构建一个能够同时处理两者的巨大的、“异构”的数据结构？例如，你可以将所有IPv4地址填充到128位，并将它们放入一个巨大的字典树（前缀树）中。但这将是一个笨拙的解决方案。IPv4前缀在一个小地址空间中是密集的，而IPv6前缀在一个广阔的空间中是稀疏的。一个统一的结构将是一个糟糕的妥协，浪费内存，并可能减慢更常见的IPv4查找速度。
优雅的设计拥抱了关注点分离的原则。它认识到，虽然两者都是“IP地址”，但它们具有非常不同的特性。解决方案是使用两个独立的、同构的数据结构。对IP版本头进行一次快速的、检查，将查找定向到适当的结构。IPv4查找转到一个为32位密集空间调整的多位字典树（例如，节点更小），而IPv6查找则转到一个为128位稀疏空间优化的不同字典树（例如，步幅更大，路径压缩更积极）。这种设计不仅更快、更节省内存，而且更清晰、更易于维护。通过尊重数据中的自然划分，设计者创造了一个大于其各部分之和的解决方案。
没有什么地方的规则比金融交易所更复杂，风险更高了。一个订单簿必须根据严格的价格-时间优先规则来匹配买单（bid）和卖单（ask）：最佳价格获胜，如果价格相等，则最旧的订单获胜。
没有一个单一的、现成的数据结构可以强制执行这个两级规则。优先队列可以处理价格，但时间呢？队列可以处理时间，但价格呢？优美的解决方案是一个直接对规则逻辑进行建模的复合数据结构。
我们可以使用两个主要的优先队列，一个用于买单（一个最大堆以找到最高出价），一个用于卖单（一个最小堆以找到最低要价）。但这些堆中的节点不是存储单个订单，而是代表价格水平。与每个价格水平节点相关联的值则是另一个数据结构：一个简单的FIFO队列，按时间顺序包含在该价格提交的所有订单。要找到最佳买价和卖价（即价差），我们只需查看两个堆的顶部。要执行交易，我们从堆中弹出一个元素，然后从相关联的队列中出队。为了快速取消特定订单，我们可以添加一个哈希映射，将订单ID直接指向其在队列中的节点。这种分层设计——一个由队列组成的堆，并辅以一个哈希映射——是价格-时间优先规则的物理体现。
在科学计算中，“数据”往往是空间本身的结构。在材料受应力变形的多尺度模拟中，我们可能有数百万个原子和一个计算网格，该网格在缺陷附近是精细的，在其他地方是粗糙的。一个关键任务是找到某个原子在一定半径内的所有邻居以计算力。另一个是找到给定原子属于哪个网格元素。
这些是同一个问题吗？两者都是“空间搜索”。但一个好的设计者知道它们有天壤之别。
这个教训是，数据结构是观察数据的镜头。设计者的工作是选择能够以最小的失真和努力将所需信息聚焦的镜头，而这个选择完全取决于数据的结构和所提问题的性质。
到目前为止，我们已经看到了为速度优化和符合问题逻辑的设计。但有时，设计会开辟全新的功能，为我们能用数据做什么增加了新的维度。
通常，当我们更新一个数据结构时，旧版本就永远消失了。但如果我们想保留它呢？如果我们想从一个单一的现在探索多个可能的未来，而又不想每次都付出复制整个世界的巨大成本呢？这就是*持久化数据结构*的领域。
想象一下为棋盘游戏设计一个AI。为了决定下一步棋，AI需要进行前瞻性搜索，探索不同走棋序列的后果。一步棋会改变游戏状态。如果在搜索树中为每一个假设的走棋都复制整个棋盘状态，我们将很快耗尽内存和时间。
持久化提供了一个优雅的解决方案。我们将游戏状态表示为一个树（例如，一个线段树），而不是一个扁平的数组。当走一步棋时——比如说，在某个位置翻转一个棋子——我们不修改现有的树。相反，我们使用*路径复制*。我们创建一个新的根，并且只复制从根到被改变叶子节点的路径上的节点。这条路径很短，通常是对数高度。所有其他节点——绝大多数结构——都被简单地指向并与前一个版本共享。
这以极小的成本（）创建了一个新的、独特的游戏状态版本，而旧版本则保持完好无损且可访问。AI现在可以探索游戏树的无数分支，每个状态都是前一个状态之上的一个轻量级、半透明的叠加。这种结构共享的美妙思想是函数式编程语言、像Git这样的版本控制系统以及软件中撤销/重做功能的基础。它为数据增加了一个时间维度，让我们能够在其历史和潜在的未来中导航。
也许数据结构设计最深刻的应用不是表示数据，而是表示知识、逻辑和证明。在自动定理证明器或证明助手中，系统操纵数学表达式，应用推理规则，并构建证明。
表达式本身是异构的——它们可以是变量、常量、函数应用或抽象（-项）。证明是一棵树或一个有向无环图（DAG），其中节点是推理步骤，边连接前提和结论。一个至关重要的要求是，相同的子表达式应该由内存中同一个对象表示，这不仅是为了效率，也是为了能够通过简单的指针比较瞬间检查逻辑相等性。
这引出了一种称为哈希共享（hash-consing）的设计。每当构造一个新项时，首先根据其结构及其子项的唯一句柄对其进行哈希。系统在一个全局表中查找这个哈希值。如果该项已存在，则返回现有对象的句柄。如果不存在，则创建一个新的、不可变的对象并存储在表中。这确保了任何给定的逻辑表达式在内存中都只有一个规范的表示。此外，像-演算中的-等价（其中绑定变量名无关紧要）这样的微妙之处，可以通过在哈希之前对其进行规范化来处理，例如，使用de Bruijn索引。
在这里，数据结构不仅仅是一个容器。它是逻辑语言的体现，提供了一个框架，在这个框架中，复杂的思想可以被唯一地表示、最大程度地共享并即时比较。
我们以最深层的联系结束我们的旅程——在这里，问题的数学结构和数据结构的设计合二为一。这发生在稀疏矩阵计算领域，它几乎是所有大规模科学模拟的核心，从结构力学到流体动力学和电路仿真。
当求解线性方程组，其中矩阵是大的稀疏矩阵（大部分为零）时，一个关键步骤是计算其Cholesky分解，。在这个过程中可能会发生一件可怕的事情：填充（fill-in）。在中为零的位置在因子中可能变为非零，从而消耗内存并增加计算成本。预测和管理这种填充是一个核心挑战。
解决方案来自图论的一个惊人洞见。对称矩阵的稀疏模式可以表示为一个图，其中如果矩阵项非零，则节点和之间存在一条边。Cholesky分解的过程可以看作是从这个图中“消除”顶点的过程。填充边精确地对应于使图成为*弦图*（一个任何长度大于等于四的环都有捷径的图）所需的边。
这个最终的、填充后的弦图的结构告诉了我们需要知道的一切。因子中的非零元对应于这个图的边。更美妙的是，存储和计算这个因子的最有效方法是找到这个弦图的团树——一个由图的最大完全连接子图构成的树。因子所需的总存储量恰好是每个团的存储量之和，减去它们交集中的重叠部分。这不是一个近似值；这是一个数学恒等式。最优的数据结构不仅仅是受问题图结构的启发；它就是问题的图结构，被重新诠释了。
从链表中指针的简单舞蹈，到矩阵因子与图之间深刻的同构，数据结构的设计是一个在组合中寻找优雅和力量的故事。它是支撑我们数字文明的无形架构。通过理解数据、操作、硬件以及我们问题的深层数学结构，我们能够打造出不仅正确，而且高效、优雅和优美的解决方案。原则虽少，但其组合无穷——这是对精心组合的简单思想之持久力量的证明。