Balanced Tree - B-Tree

Giriş

B-Tree klasik anlamda bir Binary Tree değildir. 

Balanced Search Tree Nedir?

Açıklaması şöyle

Balanced search trees are the trees in which the difference between any 2 paths from the root to a leaf node is not bigger than 1. Balanced search trees are used to work with sorted data and provide insert/delete/search operations with time complexity O(log n). A popular implementation of the binary balanced search tree is the red-black tree (which is a simplified implementation of a 2–3 search tree)

If we have a red-black tree that is quite small, we can store it in memory, and perform all search and modification operations extremely fast. But what happens when the data is huge and It doesn’t fit into memory? In this case, it is stored on the disk. I say the disk, but the more correct name is block-oriented storage. Block storage is when data is split into fixed-size blocks and then these blocks are stored as separated pieces. Databases usually work with such storage.

Imagine we have a red-black tree and store it in the block storage. The data of the tree will be spread into different blocks. When doing any operation with the tree, e.g. search, we need to fetch data from different blocks. But, the time required to fetch data from the block is large than the time to access data within a block. How could we decrease the number of fetches?

Here is when B-tree appears. B-tree is a generalization of balanced search trees with the purpose of having a minimum number of disk reads when accessing the needed data. The main idea is not to store only 2 or 3 keys per node but a large number, the number of keys that can fit in the block (page).

Page

Açıklaması şöyle

B-Tree is the most widely used indexing data structure in almost all relational databases.

The basic unit of information storage in B-Tree is usually called a “page”. To look up a key, it traces down the range of keys until the actual value is found.

Sıralı Olması

En büyük avantajı sıralı olmasıdır. Açıklaması şöyle

While the advantages of the B-Tree are numerous, the main advantage for our purposes is that it is sortable. When the data structure is sorted in order it makes our search more efficient...

Şeklen şöyledir

Aynı şekil şöyle de gösterilebilir

B-Tree vs LSM-Tree

Açıklaması şöyle

LSM-Tree (Log-Structured Merge Tree) is widely used by many NoSQL databases, such as Cassandra, LevelDB, and RocksDB.

LSM-trees maintain key-value pairs and are persisted to disk using a Sorted Strings Table (SSTable), in which the keys are sorted.

Level 0 segments are periodically merged into Level 1 segments. This process is called 𝐜𝐨𝐦𝐩𝐚𝐜𝐭𝐢𝐨𝐧.

The biggest difference is probably this:
  -B-Tree enables faster reads
 - LSM-Tree enables fast writes

Şeklen şöyle