B-Tree

B-Tree 

  • The Most widely used indexing structure is B-Tree - Mostly in relational databases.
  • B-Tree keeps key-value pairs sorted by key.
  • B-Tree breaks the database down into fixed size block or pages; 4 KB in size and read and write one page at a time.
  • Each page can be identified using an address or location, which allows one page to refer to another  - similar to pointer but on disk.
  • We can use these page reference to construct a tree pf pages.
Example:
        

One page is designated as the root of the B-Tree.

The page contains several keys and references to child pages. Each child is responsible for a continuous range of keys and the keys between the references indicate where the boundaries between those ranges lies.

Eventually we get down to a page containing keys (a leaf page), which either contains the value for each key inline or contains references to the pages where the values can be found.

Branching Factor : 

The number of references to the child pages in one page of the B-tree is called the branching factor.
Branching factor depends on the amount of space required to store the page references and the range boundaries.
Typically it is several hundreds.

B-Tree Algorithm : 

  • The algorithm of B-Tree ensures that the tree remains balanced.
  • A B-Tree with N keys always has a depth of O(logN). Most databases can fit into B-Tree that is three or four levels deep, so you do  not need to follow many pages to find the page you are looking for.
  • A four level tree of 4 KB page with branching factor of 500 can store up to 256 TB data.
  • Algorithm follows this:
    • If you want to add a new key, you need to find the page whose range encompasses the new key and add it to that page.
    • If there is not enough space in the page to accomodate the new key, it is split into two half-full pages, and the parent page is updated to account for the new subdivision of key ranges.
The basic underlying write operation of a B-Tree is to overwrite a page on disk with new data.
while in LSM-Tree, write operation only append to log file.
Also, sometime, you split page and update references in parent page. All this happens on disk.
To make database resilient, it includes an additional concept: a write ahead log.

Write Ahead Log (WAL) :

This is an append only file, to which every B-Tree modification must be written before it can be applied to the pages of tree itself.
If the database crash and comes back, this log is used to restore the B-Tree back to a consistent state.

Concurrency : 

Concurrency is done by protecting the tree's data structure with latches (light weight locks).
Log structured approaches are simpler in this regards, because they do all the merging in the background without interfering with incoming queries.

Comments

Post a Comment

Popular posts from this blog

Distributed Lock with Redlock

 Distributed Lock with Redlock Distributed lock systems are used to ensure that only one process or thread can access a particular resource at a time. Redlock is a distributed lock system that was introduced by Redis. The goal of Redlock is to provide a reliable and fault-tolerant distributed lock service.   The Redlock system is designed to work in a distributed environment where multiple instances of a service or application can run concurrently. Each instance of the application can acquire a lock and perform some operations on the resource. The Redlock system ensures that only one instance of the application has access to the resource at a time.   Components of Redlock :   Lock Manager : The Lock Manager is responsible for managing the lock state and deciding which instance of the application can acquire the lock. It receives requests from the applications to acquire or release the lock.   The Lock Manager uses a distributed consensus algorithm to en...
Read more

Distributed Transaction

Distributed Transaction A distributed transaction across multiple database services involves multiple databases that are geographically distributed across  different locations .       Here are some important steps to consider when designing a system for distributed transactions across multiple database services:     Transaction Protocol      Transactional consistency      Concurrency control      Reliability and Fault-tolerance      Performance   Transactional Protocol A distributed transaction protocol is a set of rules and procedures that define how a distributed transaction should be executed across multiple databases .   It is used for Atomic commit across databases    There are several distributed transaction protocols to choose from, each with its own advantages and disadvantages.     Two-Phase Commit (2PC ) :   It is a widely-used protocol that ensures at...
Read more

Storage Engine

Image
Database Storage Engine Two kinds of database storage engine are most popular: Log Structured Storage Engine (SSTable, LSMTree) Page Oriented Storage Engine (B-Tree) Log Structured Storage Engine  Most of the databases internally use a log, which is an append only data file. Log file is an append only sequence of records It is not human readable, binary file Issues Since log file is append only file, so it keeps growing, hence resulting performance issue. While reading data, every time it looks from beginning Performance degrades if number of records are more in the database To mitigate these issues, a new concept came out called Indexing. Index In order to efficiently find the value for a particular key in the database, we need a different data structure, this is called an Index. In General the idea behind them is to keep some additional metadata on the side, which acts as a signpost and helps you to locate the data you want. If you want to search some data in a several different ...
Read more