4nf*_*3rt 6 database time-complexity data-structures
我试图理解X和Y Fast Trie数据结构,并且不清楚为什么这些结构不在大型数据库中使用,因为它们的渐近复杂度小于Log(N).在我们有太字节数据库的情况下,使用Y Fast Trie比使用B树更好吗？
小智 6
虽然templatetypedef似乎给出了详细的答案,但答案中的大多数观点都不正确.让我一一驳斥:
- X-fast尝试内部需要几个链接结构...在数据库环境中表现不佳......
X-fast尝试基本上是在度量空间上定义的二叉搜索树.有一些技术可以将二叉树组织成合理的页面.双链接结构看起来很糟糕,但是在找到后继者之前不会调用指针.这只是一次磁盘搜索.
- X-fast尝试内部需要使用完美的哈希表...
这不是真的.您可以使用任何散列技术.为了保证恒定的时间查找,您可以使用布谷鸟哈希而不是完美的哈希.
- 由于X-fast尝试中的哈希表...只能有效地分摊,而不是最坏情况下...
那也不是真的.如果您使用完美散列或布谷鸟散列,将保证持续的查找时间.插入/删除时间将分摊,但对于搜索密集型系统(例如Lucene)来说,这并不算太糟糕.大多数现代搜索引擎都建立在牺牲写入时间以促进搜索的基础上.
- 在X-fast尝试和Y-fast尝试中使用散列表意味着在数据结构的运行时中涉及随机元素...
这取决于系统的目标.只有当您想要支持可靠和高效的写入时,上述陈述才适用.但对于大多数面向搜索的应用程序,您的首要任务是提高搜索速度.
- 由于上面列出的所有原因,埋在X-fast和Y-fast尝试运行时的常数因子非常大......
确实,常数因子并非微不足道 - 但我会惊讶地发现任何超过4的东西,并考虑loglogM时间(例如,64位宇宙中的6),这没什么.
那么Y-fast尝试的工业应用如此之少的真正原因是什么呢？数据库行业是一个利润丰厚的大型企业,在采用新技术方面往往很慢.直到20世纪90年代末,R树才被广泛采用.尽管理论上成熟,但面向对象的概念一直被业界所拒绝.他们的DB人员一直拒绝B-trees以外的任何东西,直到像Lucene这样的开源搜索引擎几乎在搜索相关业务的所有领域都击败了RDBMS.就在上个月,一位资深甲骨文家伙告诉我,基于特里/哈希表的系统永远不会是实时的 - 直到我向他展示如何使用内存缓存/合并.
X-fast或Y-fast尝试在实践中可能没有用的原因有几个.以下是一些:
X-fast尝试内部需要几个链接结构,包括按位trie和双链接元素列表.这些在数据库环境中表现不佳,其中元素存储在磁盘上,并且在指针之后可能需要磁盘搜索.(出于类似的原因,数据库通常使用B树而不是二叉搜索树).此外,它们需要使用平衡的二进制搜索树来增加信息以执行拆分或连接,这增加了额外的空间并引入了更多的指针.
X-fast尝试内部需要使用具有最坏情况O(1)查找的哈希表.具有这些要求的哈希表通常需要应用各种哈希函数来查找元素,并且(通常来说)与线性探测哈希表相比没有最佳的局部性,因此查找速度稍慢一些.
由于X-fast尝试中的哈希表以及在Y-fast尝试中使用BST的拆分和连接,这两个数据结构只是分摊有效而不是最坏情况有效.在某些情况下,这是不可接受的 - 如果定期数据库查询最终需要100倍或1000倍的正常时间,即使平均一切都运行得很好,也会很糟糕.
在X-fast尝试和Y-fast尝试中使用散列表意味着在数据结构的运行时中涉及随机元素.期望它们是有效的,但由于运气不好,数据结构的运行时可能会非常高.具体而言,在内部哈希表中进行重新散列或在树上进行拆分或连接的成本可能非常高.在数据库实现中,可靠性很重要,因此这种随机性可能会受到影响.
由于上面列出的所有原因,埋在X-fast和Y-fast尝试运行时间中的常数因子非常大.从长远来看,它们最终应该比其他数据结构更快,但"长期"可能需要比可能适合数据库的各种数据集大得多的输入.
希望这可以帮助!