我知道如何在内存中实现b树,但不清楚如何在光盘中存储trie。我认为主要有两点区别:
- 内存指针和磁盘地址之间的转换,看这个.
- 插入新的k/v项时如何拆分页面?在内存中很容易实现。
Thanks
这完全取决于您使用的 DBMS。如果您想知道它是如何在 MS SQL Server 中实现的,需要阅读以下内容:
- 页面(我猜它们几乎存在于所有现代 DBMS 中) - 在 SQL Server 中它们是 8Kb。数据库文件由页面组成。
- 范围 - 8 个连续页面的逻辑组
- (S)GAM -(共享)全球分配图。包含有关空闲和占用范围信息的位图。这是数据库文件的第一页。
- IAM - 索引分配图。您可以找出哪个索引/堆存储在哪些盘区中。有了这些信息,您就可以在存储索引/堆的文件中找到位置。
使用 IAM 和 GAM(或 SGAM),您可以拆分页面 - 只需将页面的一部分(应该是溢出的)移动到文件上的另一个页面。
IAM 和 GAM 也是您第一个问题的答案。
这些名称大部分取自 MS SQL Server,但我很确定,在其他 DBMS 中,它的解决方式非常相似。
希望能帮助到你。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)