可扩散列

作者: Sun东辉 | 来源:发表于2022-05-12 18:22 被阅读0次

如果需要处理的数据量太大以至于装不进去主存,我们就要考虑检索数据所需的磁盘存取次数了。

我们假设在任意时刻都有 N 个记录要存储,N 的值随时间而变化。此外,最多可把 M 个记录放入一个磁盘区块。

如果使用开放定址散列法或分离链接散列法,那么主要的问题在于,在一次 Find 操作期间,冲突可能引起多个区块被考察,甚至对于理想分布的散列表也在所难免。不仅如此,当表变得过满的时候,必须执行代价巨大的再散列这一步,它需要 O(N) 次磁盘访问。

一种聪明的选择叫作可扩散列(extendible hashing),它允许用两次磁盘访问执行一次 Find。插入操作也需要很好的磁盘访问。

我们都知道,B 树具有深度 O(\log{\frac{M}2}N)。随着 M 的增加, B 树的深度降低。理论上我们可以选择使得 B 树的深度为 1 的 M。此时,在第一次以后的任何 Find 都将花费一次磁盘访问,因为据推测根节点可能存在主存中。这种方法的问题在于分支系数(branching fator)太高,以至于为了确定数据在哪片树叶上要进行大量的处理工作。如果运行这一步的时间可以缩减,那么我们就将有一个实际的方案。这正是可扩散列使用的策略:

可扩散列使用的策略

上图是一个可扩散列的扩展实例。具体的过程为,插入 100100 时,它将进入第三片树叶,但是第三片树叶已经满了,没有空间存放它。因此我们将这片树叶分裂成两片树叶,它们由前三位确定(左图的树叶由前两位确定)。这时,需要将目录的大小增加到 3。注意,此时,所有未被分裂的树叶现在各由两个相邻目录项所指。因此,虽然重写整个目录,但是其他树叶都没有被实际访问。

如果现在插入关键字 000000,那么第一片树叶就要被分裂,生成两片树叶,故此时,目录中所做的唯一变化是 000 和 001 指针的更新。如下图:

插入关键字 000000

这个非常简单的方法提供了对大型数据库 Insert 操作和 Find 操作的快速存取时间。这里,还有一些重要的细节尚未考虑:

  • 首先,有可能当一片树叶的元素多余 D+1(D代表根所使用的位数) 个前导位相同时需要多个目录分裂。例如,从前面的例子开始,D =2,如果插入 111010、111011,并在最后插入 111100,那么目录大小必须增加到 4 以区分五个关键字。这是一个容易考虑到的细节,但是千万不要忘记它。
  • 其次,存在重复关键字(duplicate key)的可能性;如存在多于 M 个重复关键字,则该算法根本无效。此时,需要做出某些其他的安排。

这些可能性指出,这些位完全随机是相当重要的,这可以通过把关键字散列到合理长的整数(由此得名)来完成。

树叶的期望个数为 (N/M)\log_2 e。因此,平均树叶满的程度为 \ln 2 = 0.69。这和 B 树是一样的,其实这完全不奇怪,因为对于两种数据结构,当添加第 (M+1)项时,一些新的节点就建立起来了。

更惊奇的结果是,目录的期望大小(换句话说即 2^D)为 O(\frac{N^{1+\frac{1}{M}}}M)。如果 M 很小,那么目录可能过大。这种情况下,我们可以让树叶包含指向记录的指针而不是实际的记录,这样可以增加 M 的值。为了维持更小的目录,我们为每个 Find 操作添加第二个磁盘访问。如果目录太大装不进主存,那么第二个磁盘怎么说也还是需要的。

相关文章

  • 可扩散列

    如果需要处理的数据量太大以至于装不进去主存,我们就要考虑检索数据所需的磁盘存取次数了。 我们假设在任意时刻都有 N...

  • 愿疫情早日得到控制

    新型冠状病毒肺炎来势汹汹,昨天222列,今天公布的已经有308列了,扩散的迹象很明显,浙江今天确认有5列,疑似有1...

  • 断舍离~~bye~~我的甲沟炎

    初起时一侧甲沟发生红肿疼痛,短时间内可化脓感染,可扩散至指甲根部和对侧甲沟,形成指甲周围炎,也可扩散至甲下形成甲...

  • Houdini学习笔记 | Applied Houdini -

    IsoOffset节点 可以基于原几何体生成offset关系的数据,数值>0 向外扩散,最多可扩散至物体bound...

  • 散列

    散列值与相等性 等值对象的散列值必须相等。散列相等未必等值。 散列表算法 其他说明 key必须是可散列的。可散列需...

  • 画画的步骤

    白夜的颜料虽然扩散一般,但是颜色真的可呀。

  • 构建艺术新共识

    总体而言现有的艺术的共识是由精英阶层形成然后扩散开来的,列朝列代,艺术珍品也是以皇家 和 宫廷的博物馆和收藏为典范...

  • Table固定列,其余列可水平滚动

  • 扩散

    天天窝在家里实在烦。前段时间天天下雨,昨天明知没啥事也上县去转了一趟。 大概是9点到县城西门口,老远就望到右手边那...

  • 扩散

    3.7,周六 8时起床,完成学习强国43分,订阅加1分,排名仍为11,无变动。 国外确诊病例已达17000,全球近...

网友评论

    本文标题:可扩散列

    本文链接:https://www.haomeiwen.com/subject/ctenjrtx.html