Database indexing is a method used to improve the query execution on a database table. It helps optimize query performance by reducing the amount of data that needs to be scanned to satisfy a query

But indexing has associated cost of additional space and some overhead during write operations. Throughout this article we will consider postgres database to better understand how indexing works.

There are various types of indexes that are available, and choice of index depends on how data has to be organised. Lets take look at various types of indexes available:

• btree
• gin
• hash
• lsm

B*Tree Index

Most commonly used is B-Tree index, which essentially supports queries to perform better based on sorting sequence. It operates similar to BST(Binary Search Trees)

Binary Search Trees

BST’s organise data in tree like structure, where all the keys from left side of root are less and on right side are greater. Example of BST is as seen below.

There are challenges with implementation of because, if the keys that are inserted into table are either in ascending order or descending order, BST will be skewed towards left or right.

Now, if the tree is skewed, worst case complexity of search operation to search for key in index becomes O(n), which is when key is last element or its not found. In order to improve the search or query performance, depth/height of tree has to be balanced. This requires implementation of self balancing BST with help of AVL, RedBlack trees etc.

AVL self balancing trees, balances the height of tree with help or rotations (LL, LR, RL, RR) i.e. when each key is inserted into index, and if height is imbalanced it has to rotate with anyone of rotation techniques to balance its height, this equally impacts write performance.

Postgres uses extended version Lehman & Yao Algorithm for implementation of B-Tree with balancing factor configurable. This will ensure to safe gurad write paths during concurrent updates, which we will discuss in next parts.

Let’s understand underlying details of index updates and how database handles these concurrent requests to insert/update/delete entries from index.

In postgres every query is handled by process, which ensures each process has its own memory allocated to perform changes as needed by query and then flush them back to pages in disk. A page is block of memory which is 8kb by default. There can be multiple such processes operating on index, they can conflict paths when they are attempting to insert/update/delete them. There can be only one single process that can be allowed to update pages at leaf node for given page, which happens by obtaining exclusive write lock.

B-link-Tree for Concurrency

B link tree is an extension of B*-tree with an additional right pointer on the leaf nodes to access next page. This addition of right link will help during the page splits, i.e. when new key is inserted and leads to page split, a new right link is added from old page to new page.

Here are few rules that we need to understand from Lehman & Yao algorithm:

• Each node can have k +1 childrens, where k is configurable parameter
• Each node can store at max 2*k elements, if k=2 they can hold max 4 keys in node

• high-key: Every node will have an additional attribute called high key to store highest value.

• Safe Operation — Any operation that does not require page split, is considered as safe operation. If there is room to accommodate new key, it doesn’t require split.

• UnSafe Operation — Any operation that require page split, is considered as safe operation.

Insertion

Lets consider k=2 which means each node can store 2*k i.e. 4 keys in its page. Now when we attempt to insert key=3 into table, this will require index to be updated. During this process as shown in below, this will require a page split to accommodate new insertion.

The purpose of the link pointer is to provide an additional method for reaching a node. When a node is split because of data overflow, a single node is replaced by two new node. The link pointer of the first new node points to the second node; the link pointer of the second node contains the old contents of the link pointer field of the first node.

Link pointer serves as a “temporary fix” that allows correct concurrent operation, when a new node is added as part of split operation all the hierarchies must be updated accordingly, and this is done by subsequent processes. If the search key exceeds the highest value in a node, it indicates that the tree structure has been changed, and that the twin node should be accessed using the link pointer.

Search

During query execution to search for element, it performs an index scan and during the scan process if it notices that if search key k is more than high value in node, then it infers that previous operation has changed structure and searches for element through next link and updates its hierarchies. It will be able to determine if search k actually exists in the index.

While Lehman & Yao Algorithm only speaks about addition of new right link pointer, postgres specifically adds new left link pointer as well to support scans backward, ensuring that once we descend to leaf pages in tree, we do not have to recurse back to its parent for scanning instead user their left and right pointers.