既有内存效率又有磁盘空间效率的树?

问题描述 投票:0回答:1

我最近开始详细阅读有关数据结构的文章。我碰到了树。设计AVL树时考虑了快速的内存访问,而设计B树时考虑了有效的磁盘存储。假设我要设计一个既具有内存效率又具有磁盘存储效率的树,那么我应该使用哪棵树?有什么方法可以组合AVL树和B树吗?还有其他树可以同时做这两种吗?在现实世界中,这从根本上可行吗?

data-structures tree binary-tree avl-tree b-tree
1个回答
0
投票

我想设计一个既有内存效率又有磁盘存储效率的树(...)有什么方法可以将AVL树和B树结合起来?

简短的答案是没有,没有答案,除非您在数据结构领域有了突破性的发现。两者的设计都考虑到了特定的优化要求,您不能兼顾两者。

[计算中有一个称为Space–time tradeoff的概念,可以将其扩展到其他类型的折衷方案中,例如您感兴趣的折衷方案。您可以这样考虑:提高已经优化的算法的属性,您将拥有会使另一种情况恶化(除非您发现一种新方法,以前没人想过)。

我建议您看一下优化的Binary Trees的可用实现,并从最适合您的需求开始。

© www.soinside.com 2019 - 2024. All rights reserved.