1

奇客Solidot | 理论突破提升数据存储效率

 2 years ago
source link: https://www.solidot.org/story?sid=69672
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

理论突破提升数据存储效率

wanwan (42055)发表于 2021年11月18日 18时32分 星期四 新浪微博分享 豆瓣分享 来自超能第七感·碰撞
包括 MIT 计算机科学博士生 William Kuszmaul 在内的三名研究人员的发现可以提高计算机数据存储和检索的效率。这项发现与“线性探测哈希表（linear-probing hash tables）”有关，于 1954 年引入，是当今可用的最古老、最简单和最快的数据结构之一。数据结构提供了在计算机中组织和存储数据的方法，哈希表是最常用的方法之一。在线性探测哈希表中，可存储信息的位置位于一个线性数组中。

Kuszmaul 表示，假设一个数据库旨在存储 10,000 个人的社会保障号码。“我们获取你的社会保障号码x，然后我们将计算x的哈希函数 h（x），它会为你提供一个 1 到10,000之间的随机数。”下一步是将随机数h（x）移到数组中的相应位置，然后将社会保障号码x放入该位置。

Kuszmaul 表示，如果该位置已被占用，“你只需要向前移动到下一个闲置位置然后将其放入。这就是‘线性探测’一词的由来，因为你一直线性前进，直到找到一个空位。”为了稍后检索社会保障号码x，你只需要前往指定位置 h（x），如果它不在那里，就继续前进，直到你找到 x，或者到达一个闲置位置并得出结论：x不在你的数据库之中。

删除项目（例如社会保障号码）的协议略有不同。如果你在删除信息后，在哈希表中留下一个空位，那么当你之后试图寻找其他内容时就可能造成混淆，因为该空位可能错误地表明你在寻找的项目不在数据库中。为 了避免这个问题，Kuszmaul 解释说，“你可以去元素被删除的地方放上一个叫作‘墓碑(tombstone)’的小标记，表明这里曾有一个元素，但现在已被删除了。”

这个程序已使用了半个多世纪。在此期间，几乎每个使用线性探测哈希表的人都认为，如果你让它们变得太满，那么长长的、被占据的位置就会聚集在一起形成“集群”。结果找到一个空位所花费的时间会急剧增加——事实上是二次方的——时间长到不现实。因此人们接受了以低容量操作哈希表的培训——这种做法会影响企业必须购买并维护的硬件数量，从而造成经济损失。

但是这个由来悠久、一直不利于高负载率的原则已被 Kuszmaul 和他的同事——石溪大学的 Michael Bender 和 Google 的 Bradley Kuszmaul 的工作彻底颠覆。他们发现，对于插入和删除数量大体相等的应用程序——添加的数据量大致等于删除的数据量——线性探测哈希表可以在不牺牲速度的情况下以高存储容量运行。

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK