B-tree Indexing

A B-tree index is a balanced tree data structure commonly used in databases to efficiently organize and search large volumes of data.
B-trees are very similar to binary search trees (BST), but the nodes in a B-tree can have more than two children. You can learn more about BSTs in the Algorithms and Data Structures Overview course.

B-tree stores keys in sorted order within nodes, allowing for fast retrieval of data through hierarchical traversal from the root to the leaf nodes. B-tree indexing is well-suited for range queries and equality searches, making it a popular choice for optimizing database performance.

How does it work?

B-tree index organizes data in a hierarchical manner, with each node containing a fixed number of keys and pointers to child nodes.
B-trees maintain balance by ensuring that all leaf nodes are at the same level, which optimizes search operations.
When searching for a particular key, the B-tree algorithm traverses the tree from the root node down to the leaf nodes, utilizing binary search to efficiently locate the desired key.

Index lookup involves traversing the tree to reach leaf nodes, following the leaf node chain to find matching records, and retrieving the actual data from the disk.

In the figure, the lookup for key 302 is shown:

1. A search tree structure is a type of tree where each node has two pointers: the left pointer points to child nodes with values smaller than the parent node, and the right pointer points to child nodes with values larger than the parent node;

2. In a B-tree, the root node can contain multiple index values. For example, if the root contains three distinct values, it will have three pointers, each indicating the range of values between those key values;

3. To search for a key, such as 302, the search starts at the root node and follows the appropriate pointers down to the leaf nodes. The search is completed after traversing three tree blocks, as shown in the diagram highlighted in red;

4. To search for a range of values starting from 302, you can use the horizontal pointers between the leaf nodes. For instance, retrieving values from 302 to 502 is done by following the leaf nodes sequentially.

Note

The key used for searching in a B-tree index comes from the values stored in the indexed column(s) of the database table. For example, if the index is on a column like "client_id", the search key will be the actual "client_id" values. Each unique numerical value in the indexed column serves as a key in the B-tree index, making it easier to find and retrieve the corresponding rows in the database table.

Pros and cons

Unlike the standard Binary Search Tree data structure, B-tree nodes can accommodate more than 2 children. The default maximum number of children per node is typically set to 16.

Index implementation

To create a B-tree index on a column in PostgreSQL, you can use the following SQL command:

As the B-tree index is a default index in SQL, we can also use the following statement to create it:

Note

In SQL, when you create a table with a primary key constraint, most database management systems automatically create an index on the column(s) specified in the primary key. This index helps enforce the uniqueness constraint of the primary key and also improves the performance of queries that involve searching or joining based on the primary key column(s).