B+ Tree: How Oracle DB works

• Author
• Recent Posts

Ankit Verma

Geek is the best word, I can find to describe Ankit. Bringing more than a decade extensive experience of the industry, he never sits back and relaxes, always experiments with technology advancements, but at the same time, he is a good father, husband,son, brother and a fantastic friend. A bit introvert Ankit takes sometimes to open up.

When not doing programming software, he will be programming family outing.

Latest posts by Ankit Verma (see all)

• Microservices Pattern – Shared Data - February 21, 2021
• Event Sourcing – Data Integrity - January 23, 2021
• CQRS ( Command Query Responsibility Seggregation) - January 8, 2021

B+ Tree 

Continuing from the previous topic LSM and SSTables now let’s talk about B+ Trees. Now let’s understand how this works and see the main operations.

As we know that LS indexes break the database down into variable size segments typically several MB is more in size, and always write a segment sequentially. By contrast, B-Tree breaks the DB into fixed-size blocks or pages, traditionally 4KB in size and one read and write one page at a time.

This design corresponds more closely to the underlying hardware, as disks are also arranged in fixed-size blocks. 

Each page can be classified using an address or location, which allows one page to refer to another similar to a pointer, but on disk instead of a memory. We can use these page references to construct a tree of pages.

One page will be designated as the root of the B+ tree. This page contains several keys and references to child pages. Each child is responsible for a continuous range of keys, and the keys between references indicate where the boundaries between ranges lie.

The number of references to child pages in one page of the B+ Tree is called the Branching Factor.

Update In B+ tree

If you want to update the value for an existing key in B+ Tree, you search for the leaf page containing that key, change the value in the page and write the page back to disk.

Insert In B+ tree

If you want to add a new key, you need to find the page whose range encompasses the new key and it to that page.

Why B+ Trees are reliable

The basic underlying write operation of the B+ tree is to overwrite a page on disk with new data. It is assumed that the overwrite does not change the location of the page.

Some operations require several different pages to be overwritten. If you split a page because an insertion caused it to be overfull you need to write two pages that were split and also overwrite their parent pages that were split and also overwrite their parent pages to upgrade references to the two-child pages.