DEV Community

Muhammad Farooq
Muhammad Farooq

Posted on

3

B-Tree indexes in PostgreSQL and Search by Equality in It.

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

A simple B-tree Image taken from https://postgrespro.com/blog/pgsql/4161516

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

Searching 49 with equality in B-tree

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

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay