btree如何存储在光盘上？ [英] How btree is stored on disc?

问题描述

我知道如何在内存中实现btree，但不清楚如何在光盘中存储btree。我认为有两个主要区别：

1. 内存指针和磁盘地址之间的转换，请参阅 post 。


2. 如何在插入新的k / v项目？

$ b

感谢

解决方案

这一切都取决于你使用的DBMS。如果你想知道它是如何实现在MS SQL Server，阅读的事情是：






• 页面（我猜他们几乎都在现代DBMS） - 在SQL Server中，它们是8Kb。


• 范围 - 8个连续页面的逻辑组


• （S）GAM - （共享）全局分配映射。位图包含有关空闲和占用的区域的信息。这是数据库文件中的第一个页面。


• IAM - 索引分配映射。您可以找到哪个索引/堆存储在哪些区域。






使用IAM和GAM（或SGAM），您可以将其存储在存储索引/堆的文件中。可以拆分页面 - 只需将页面的一部分（应该溢出）移动到文件上的另一个页面。





IAM和GAM也是第一个问题的答案。





这些名称大部分来自MS SQL Server，但我相信，在其他DBMS中，它的解决方法非常相似。





希望它有帮助。




I know how to implement btree in memory, but not clear about how to store btree in disc. I think there are two major difference:

1. Conversion between memory pointer and disc address, see this post.
2. How to split page when insert new k/v item? It is very easy to implement in memory.

Thanks

解决方案

it all depends on DBMS you use. If you wanna know how it is implemented in MS SQL Server, things to read about are:

• Pages (I guess they are in almost all modern DBMS's) - in SQL Server they are 8Kb. Database file is composed from pages.
• Extents - logical groups of 8 continous pages
• (S)GAM - (Shared) Global Allocation Map. Bitmap containing information about free and occupied extents. This is one of the first pages on database file.
• IAM - Index Allocation Map. You can find out which index/heap is stored in which extents. Having this information, you can get place in the file where index/heap is stored.

Using IAM and GAM (or SGAM) you can split page - just move part of the page (which is supposed to be overflowed) to the another page on file.

IAM and GAM are also answers to your first question.

Most of these names are taken from MS SQL Server but I'm pretty sure, that in other DBMS's it is solved quite similar.

Hope it helps.

这篇关于btree如何存储在光盘上？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！