Why There’s No Single Best Way To Store Information

In data storage, sometimes it’s best to embrace a bit of disorder.

在数据存储中，有时最好接受一点无序性。

Kristina Armitage/ Quanta Magazine

克里斯蒂娜·阿米蒂奇/广达杂志

Just as there’s no single best way to organize your bookshelf, there’s no one-size-fits-all solution to storing information.

正如没有一种最佳的方式来组织书架一样，也没有一种放之四海而皆准的信息存储解决方案。

Consider the simple situation where you create a new digital file.

考虑创建新数字文件的简单情况。

Your computer needs to rapidly find a place to put it.

您的计算机需要快速找到放置位置。

If you later want to delete it, the machine must quickly find the right bits to erase.

如果您稍后想要删除它，机器必须快速找到要擦除的正确位。

Researchers aim to design storage systems, called data structures, that balance the amount of time it takes to add data, the time it takes to later remove it, and the total amount of memory the system needs.

研究人员的目标是设计称为数据结构的存储系统，以平衡添加数据所需的时间、稍后删除数据所需的时间以及系统所需的内存总量。

To get a feel for these challenges, imagine you keep all your books in a row on one long shelf.

为了感受这些挑战，想象一下你把所有的书都排成一排放在一个长架子上。

If they’re organized alphabetically, you can quickly pick out any book.

如果它们按字母顺序排列，您可以快速挑选出任何一本书。

But whenever you acquire a new book, it’ll take time to find its proper spot.

但每当你买一本新书时，都需要时间才能找到合适的位置。

Conversely, if you place books wherever there’s space, you’ll save time now, but they’ll be hard to find later.

相反，如果你把书放在有空间的地方，现在可以节省时间，但以后就很难找到了。

This trade-off between insertion time and retrieval time might not be a problem for a single-shelf library, but you can see how it could get cumbersome with thousands of books.

对于单书架图书馆来说，插入时间和检索时间之间的这种权衡可能不是问题，但您可以看到，对于数千本书来说，它会变得很麻烦。

Instead of a shelf, you could set up 26 alphabetically labeled bins and assign books to bins based on the first letter of the author’s last name.

您可以设置 26 个按字母顺序标记的书箱，并根据作者姓氏的第一个字母将书籍分配到书箱，而不是书架。

Whenever you get a new book, you can instantly tell which bin it goes in, and whenever you want to retrieve a book, you will immediately know where to look.

每当您收到一本新书时，您都可以立即知道它应该放入哪个垃圾桶，并且每当您想要取回一本书时，您也会立即知道该去哪里找。

In certain situations, both insertion and removal can be a lot faster than they would be if you stored items on one long shelf.

在某些情况下，插入和取出的速度可能比将物品存放在一个长架子上要快得多。

Of course, this bin system comes with its own problems.

当然，这个垃圾箱系统也有它自己的问题。

Retrieving books is only instantaneous if you have one book per bin; otherwise, you’ll have to root around to find the right one.

如果每个箱子里只有一本书，那么检索书籍只能是即时的；否则，您将不得不四处寻找合适的人选。

In an extreme scenario where all your books are by Asimov, Atwood, and Austen, you’re back to the problem of one long shelf, plus you’ll have a bunch of empty bins cluttering up your living room.

在极端的情况下，你所有的书都是阿西莫夫、阿特伍德和奥斯汀的书，你又回到了一个长书架的问题，而且你的客厅里还会堆满一堆空箱子。

Computer scientists often study data structures called hash tables that resemble more sophisticated versions of this simple bin system.

计算机科学家经常研究称为哈希表的数据结构，它们类似于这个简单的垃圾箱系统的更复杂版本。

Hash tables calculate a storage address for each item from a known property of that item, called the key.

哈希表根据每个项目的已知属性（称为键）计算该项目的存储地址。

In our example, the key for each book is the first letter of the author’s last name.

在我们的示例中，每本书的键是作者姓氏的第一个字母。

But that simple key makes it likely that some bins will be much fuller than others.

但这个简单的钥匙使得某些垃圾箱可能比其他垃圾箱更满。

(Few authors writing in English have a last name that starts with X, for example.) A better approach is to start with the author’s full name, replace each letter in the name with the number corresponding to its position in the alphabet, add up all these numbers, and divide the sum by 26.

（例如，很少有用英语写作的作者的姓氏以 X 开头。）更好的方法是从作者的全名开始，将姓名中的每个字母替换为与其在字母表中的位置相对应的数字，将所有这些数字相加，然后将总和除以 26。

The remainder is some number between zero and 25.

余数是 0 到 25 之间的某个数字。

Use that number to assign the book to a bin.

使用该编号将书籍分配到垃圾箱。

This kind of mathematical rule for transforming a key into a storage address is called a hash function.

这种将密钥转换为存储地址的数学规则称为哈希函数。

A cleverly designed hash function ensures that items will usually end up distributed relatively evenly across bins, so you won’t need to spend as much time searching in each bin.

巧妙设计的哈希函数可确保项目通常最终会相对均匀地分布在各个垃圾箱中，因此您无需花费太多时间在每个垃圾箱中进行搜索。

If you want to reduce retrieval time further, you can use more bins.

如果您想进一步减少检索时间，可以使用更多的垃圾箱。

But that leads to another trade-off: Those bins will take up space even if they end up empty.

但这会导致另一个权衡：这些垃圾箱即使最终空了，也会占用空间。

This trade-off between space and time is an inherent feature of hash tables — it’s the price you pay for avoiding the tension between insertion and retrieval time that plagues simpler data structures.

这种空间和时间之间的权衡是哈希表的固有特征——这是为了避免插入和检索时间之间的紧张而付出的代价，这种紧张会困扰更简单的数据结构。

More than 70 years after hash tables were invented, computer scientists are still discovering new things about their fundamental properties.

哈希表发明 70 多年后，计算机科学家仍在发现有关其基本属性的新事物。

Recently, they finally devised a version that strikes an ideal balance between space and time .

最近，他们终于设计出了一个在空间和时间上达到理想平衡的版本。

And last year, an undergraduate student disproved a long-standing conjecture about the minimum amount of time needed to find a specific item in a hash table that’s almost full.

去年，一名本科生反驳了一个长期以来的猜想，即在几乎已满的哈希表中找到特定项目所需的最短时间。

Hash tables work well when you can’t anticipate which piece of data you’ll need to retrieve next.

当您无法预测接下来需要检索哪条数据时，哈希表会发挥很好的作用。

But that’s not always the case.

但情况并非总是如此。

Imagine you’re trying to complete tasks on a to-do list, but you’re constantly being assigned new tasks with different deadlines.

想象一下，您正在尝试完成待办事项列表上的任务，但您不断被分配具有不同截止日期的新任务。

You want to be able to quickly add new items to the to-do list, but you don’t care about retrieving items until they become your top priority.

您希望能够快速将新项目添加到待办事项列表中，但您并不关心检索项目，直到它们成为您的首要任务。

In this case, your best bet is a type of data structure called a heap.

在这种情况下，最好的选择是一种称为堆的数据结构。

As the name suggests, a heap is a somewhat haphazard approach to data storage.

顾名思义，堆是一种有点随意的数据存储方法。

It’s basically a mathematical version of a pile of stuff: Some items are stored above others, and these higher items are easier to access.

它基本上是一堆东西的数学版本：一些项目存储在其他项目之上，并且这些较高的项目更容易访问。

The highest-priority item is always at the top of the heap, where you can instantly pluck it off.

最高优先级的项目始终位于堆的顶部，您可以立即将其取下。

Lower layers will be more disorganized, but you don’t need to worry about the relative positions of these low-priority items.

较低的层会更加混乱，但您无需担心这些低优先级项目的相对位置。

The simplest implementation of this basic idea uses a mathematical object called a binary tree, which is a network of nodes with a special shape: There’s a single node at the top, and each node is connected to two nodes directly below it.

这一基本思想的最简单实现是使用一种称为二叉树的数学对象，它是具有特殊形状的节点网络：顶部有一个节点，每个节点都连接到其正下方的两个节点。

Let’s imagine a binary tree that contains the items in a to-do list.

让我们想象一个包含待办事项列表中的项目的二叉树。

Each node can store a single item, and each item is labeled with a number that represents its due date.

每个节点可以存储一个项目，每个项目都标有一个代表其到期日期的数字。

High-priority items get smaller numbers.

高优先级项目的编号较小。

Each new item is put into an empty slot in the current lowest layer.

每个新项目都会被放入当前最低层的一个空槽中。

Once the new item goes in, compare its due date to that of the item in the node directly above it.

新项目进入后，将其到期日期与其正上方节点中的项目的到期日期进行比较。

If the new task is due sooner, swap the items.

如果新任务提前到期，则交换项目。

Keep swapping until the new item ends up directly below an item that’s more urgent.

继续交换，直到新项目直接位于更紧急的项目下方。

This procedure ensures that the highest-priority item will always rise to the top.

此过程可确保最高优先级的项目始终位于顶部。

What’s more, the procedure is extremely fast.

更重要的是，这个过程非常快。

Even in a nightmare scenario where you have 1,000 tasks on your to-do list and keep getting new assignments, storing them in a heap ensures that it takes no more than nine swaps to move each new item up to the appropriate position.

即使在噩梦般的场景中，您的待办事项列表中有 1,000 个任务并不断收到新的分配，将它们存储在堆中也可确保将每个新项目移动到适当的位置所需的交换次数不超过 9 次。

Whenever you complete the most urgent task and remove it from the heap, you can quickly pull up your new top priority from the layer below.

每当你完成最紧急的任务并将其从堆中删除时，你可以快速从下面的层中拉出新的最优先任务。

Within computer science, heaps are widely used in algorithms for finding the shortest path from a given starting point in a network to every other point.

在计算机科学中，堆广泛用于算法中，用于查找从网络中给定起点到每个其他点的最短路径。

In 2024, a team of researchers used an ingenious new heap design to transform a classic shortest-paths algorithm into one that is theoretically optimal for any network layout .

2024 年，一组研究人员使用了一种巧妙的新堆设计，将经典的最短路径算法转变为理论上适合任何网络布局的算法。

There’s no shortage of self-help books filled with contradictory advice about the best way to organize your belongings.

市面上不乏自助书籍，其中充满了关于整理物品的最佳方式的相互矛盾的建议。

If computer science offers any lesson, it’s that there is no perfect solution — every approach comes with trade-offs.

如果计算机科学提供了任何教训，那就是不存在完美的解决方案——每种方法都需要权衡。

But if some items are more important to you than others, don’t be afraid to leave a bit of a mess.

但如果某些物品对您来说比其他物品更重要，请不要害怕留下一点混乱。

Get highlights of the most important news delivered to your email inbox

获取发送到您的电子邮件收件箱的最重要新闻的摘要

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation.

《Quanta》杂志对评论进行审核，以促进知情、实质性、文明的对话。

Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected.

辱骂、亵渎、自我推销、误导、语无伦次或偏离主题的评论将被拒绝。

Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.

版主在正常工作时间（纽约时间）有工作人员，并且只能接受英文评论。