什么是四链表？

Question

我正在努力在工作中实现列表类型结构,我需要它是疯狂有效的.在我寻找有效的数据结构时,我偶然发现了一个四重喜欢列表的专利,这引起了我的兴趣,足以让我忘记我当前的任务并开始调查四元组列表.不幸的是,互联网对整个事情非常隐秘,并且谷歌在可用结果方面没有产生太多.我得到的唯一解释是专利说明:

四链接数据结构,为单个记录中的多个相关字段提供双向搜索功能.通过以N个数据条目的间隔提供指针集来搜索数据库,以适应指针的二进制搜索,随后线性搜索结果范围以定位感兴趣的项目及其相关字段.

不幸的是,这让我更加困惑,因为我不能围绕非外行解释.因此,我向大家求助,希望你能向我解释这个四联画历史到底是什么,因为我知道不知道会不会很快地把我推到墙上.

你知道四链表是什么吗？

Answer 1

我不能确定,但​​听起来有点像跳过列表.

即使它不是它,你也可以找到方便的跳过列表.(据我所知,它们是单向的,但是.)

Answer 2

我以前没有正式提到这个术语,但从专利说明中,我可以做出有根据的猜测.

链表是每个节点都有一个链接到下一个链接的列表...

a -->-- b -->-- c -->-- d -->-- null

双向链表意味着每个节点也保持与其前任的链接.

  --<--   --<--   --<--  
|       |       |       |
a -->-- b -->-- c -->-- d -->-- null

我们假设列表已排序.如果我想执行二进制搜索,我通常会在列表的一半找到中间节点,然后进入适当的间隔并重复.但是,链表遍历总是O(n) - 我必须遵循所有链接.从描述中,我认为他们只是从节点添加额外的链接以"跳过"列表中前面的固定数量的节点.就像是...

  --<--   --<--   --<--  
|       |       |       |
a -->-- b -->-- c -->-- d -->-- null
|                       |
|----------->-----------|
 -----------<-----------

现在我可以更快地遍历列表,特别是如果我仔细选择了额外的链接目标(即确保它们总是返回/转发它们从列表长度中指向的项目的偏移量的一半).然后我找到了这些链接所需的粗略间隔,并使用普通链接查找该项目.

这是我讨厌软件专利的一个很好的例子.这是非常明显的东西,用华丽的散文包裹着让人迷惑.