I understand how to implement btree in memory, although not obvious concerning how to store btree in disc. I believe you will find two major difference:

  1. Conversion between memory pointer and disc address, check this out post.
  2. How you can split page when place new k/v item? It's very simple to apply in memory.


everything is dependent on DBMS you utilize. Should you wanna understand how it is implemented in MS SQL Server, items to find out about are:

  • Pages (I suppose they're in just about all modern DBMS's) - in SQL Server they're 8Kb. Database file consists from pages.
  • Extents - logical categories of 8 continous pages
  • (S)GAM - (Shared) Global Allocation Map. Bitmap that contains details about free and occupied extents. This is among the first pages on database file.
  • IAM - Index Allocation Map. You are able to discover which index/heap is saved by which extents. Getting these details, you will get devote the file where index/heap is saved.

Using IAM and GAM (or SGAM) you are able to split page - just move area of the page (which is designed to be overflowed) towards the another page on file.

IAM and GAM will also be solutions for your first question.

Many of these names are obtained from MS SQL Server but I am confident, that in other DBMS's it's solved quite similar.

Hope it will help.

My recommendation would be to take a look in the book Database System Implementation"

Chapter 2 inchinformation storage" and chapter 3 "representing data elements" wil provide you with some hints relating to this problem.

Chapter 4 index structures includes a section on Btrees

It is the best supply of information I've discovered to date about this subject.