B-tree indexing is suitable for data that can be sorted,(equality operators such as "==", "<", "<=", ">" and ">=" can be applied on the data),
In B-tree indexing, the index rows are stored in pages. In the leaf pages, you can find the data that needs to be indexed, such as keys, and references to table rows. Whereas, the internal pages contain rows that reference child pages and indicate the minimum value in the child page.
B-trees are balanced and multi-branched, enabling fast searches for any value.
They store sorted data within and between pages in increasing order
same-level pages are connected by a bidirectional list for efficient ordered data retrieval.
below is the simplified example
The very first page, block or node of the index is a Meta page, which references the index root. Internal nodes are located below the root, and leaf pages are in the bottom most row. Down arrows represent references from leaf nodes to table rows (TIDs).
Searching 49 with equality operator
The search starts with the root node, and we need to determine to which of the child nodes to descend. since 49 lies between 32 and 64 we need to descend node with key 32, Next, the same process is recursively repeated until we reach a leaf node from which the needed TIDs can be obtained.
But wait...
look at the image, it seems that we should descend from the node 49. But, as clear from the figure, this way we will skip one of the "49" keys in the preceding leaf page.
Therefore, once we've found an exactly equal key in an internal page,
we have to descend one position left
and then look through index rows of the underlying level from left to right in search of the required key.
I hope it will help you
See More at : Indexes in PostgreSQL - (Btree)
Visit to know about Apache Age a PostgreSQL extension
Apache AGE: age.apache.org
Apache AGE (Github) : github.com/apache/age
Top comments (0)