btree是如何存储在磁盘上的?[英] How btree is stored on disc?

本文是小编为大家收集整理的关于btree是如何存储在磁盘上的?的处理/解决方法,可以参考本文帮助大家快速定位并解决问题,中文翻译不准确的可切换到English标签页查看源文。

问题描述

我知道如何在内存中实现btree,但尚不清楚如何将btree存储在光盘中.我认为有两个主要区别:

  1. 内存指针和光盘地址之间的转换,请参阅此 post .
  2. 当插入新的K/V项目时,如何拆分页面?在内存中实现非常容易.

谢谢

推荐答案

这一切都取决于您使用的DBM.如果您想知道它在MS SQL Server中的实现方式,那么要阅读的内容是:

  • 页面(我想它们几乎是所有现代DBM的) - 在SQL Server中,它们是8KB.数据库文件由页面组成.
  • 范围 - 8个连续页的逻辑组
  • (S)GAM-(共享)全局分配图.位图包含有关自由和占领的信息的信息.这是数据库文件上的第一批页面之一.
  • iam-索引分配图.您可以发现存储哪个索引/堆在哪个范围内.拥有此信息,您可以将存储索引/堆的文件放置在文件中.

使用IAM和GAM(或SGAM)您可以拆分页面 - 只需将页面的一部分(应该被溢出)移至文件上的另一页.

iam和gam也是您第一个问题的答案.

这些名称中的大多数来自MS SQL Server,但我很确定,在其他DBMS中,它的求解非常相似.

希望它有帮助.

其他推荐答案

我的建议是要看一本书数据库系统实现"

第2章"数据存储"和第3章"表示数据元素"将为您提供有关此问题的一些暗示.

第4章索引结构有关于BTREES的部分

这是我到目前为止在此主题上找到的最佳信息来源.

本文地址:https://www.itbaoku.cn/post/597715.html

问题描述

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.

其他推荐答案

My recommendation is to have a look at the book Database System Implementation"

Chapter 2 "data storage" and chapter 3 "representing data elements" wil give you some hints about this problem.

Chapter 4 index structures has a section on Btrees

It's the best source of information I have found so far on this topic.