Database Theory: What is BRIN (Block Range Index), How is faster than BTREE Index

The BRIN index is very new type of index in a Database System.

Currently we are using B-Tree indexes most, but BRIN Indexes are much faster than B-Tree Indexes.
It is not correct to say that BRIN is a 100% replacement of B-Tree but in some situation, it executes 10 times faster than B-Tree Index.

Let me provide you a small note on B-Tree as well,

The structure of B-Tree looks like a Binary Search Tree.
If you have a large table, overall branching of BTree Index is very large because it required to store thousands of keys in a B-Tree node.

The B-Tree also stored all the key values in their leaf nodes so for every search key lookups require to scan both the leaf node and B-Tree mapping node.

If we have very large table with the B-Tree index and we are selecting a large number of records, B-Tree index lookup will slow down the query performance.
The B-Tree index also takes more database space and maintenance is also very costly for a large database table.

What is BRIN (Block Range Index):
The BRIN Index

The BRIN is a new database indexing technique, mainly design for very large table.

We know about the Table Partitioing concept, which we require to implement on a very large table.
The BRIN index also works like Horizontal Table Partitioning, by creating a different block of data.
If we are using BRIN, we do not require to implement Table Partitioing explicitly.

The BRIN index creates different block of data and it defines range using MinMax function.
Every block has one Min value and Max value associated which is used to identify a related block of data.
A block range is a group of pages that are physically adjacent in the table, for each block range, some summary info is stored by the index.

The BRIN index is a very lightweight because it stores only summery of the data block. Unlike B-Tree indexes, it doesn’t require to store all key node value in index page.

An Even entire form of BRIN indexes can easily store in the memory because of its compact form and it reduces the scanning of the disk.
As it is stored only summary of block so it is also 10 times faster than B-Tree for INSERT and UPDATE operations.

The creation of the BRIN indexes on a large table are also much faster than B-Tree indexes.
The efficiency of BRIN index is also depends on the physical order of table data.

The BRIN indexes are scanning the tuples bases on a bitmap and it returns only those tuples which are matched in block range summary information so It also avoids scanning of the large parts of the table.

The B-Tree indexes are still superior for random searches, and we should use the BRIN indexes for specific type of queries which are mostly used in BIGDATA, Reporting, Data Warehouse.

Please visit next post, for one practical example of BRIN Index in PostgreSQL 9.5.

Anvesh Patel

Leave a Reply

2 Comments on "Database Theory: What is BRIN (Block Range Index), How is faster than BTREE Index"

Notify of
Sort by:   newest | oldest | most voted

I want upgrade my cluster 9.3 to 9.4 so .how can i approch.