Understanding the Basics of B-Trees

What is a DB Index?

Recently, I've been doing some database performance tuning and discovered that Prisma has this syntax: @@index
Apparently, adding this index improves database search performance.
Since I don't have much knowledge in this area, I'd like to research and summarize what an index is.

What Happens When You Add an Index?

Adding an index seems to provide the following benefits:

• Faster searches: Setting it on columns frequently specified in the WHERE clause dramatically increases read speed.
• Efficient sorting: Setting it on columns often used in ORDER BY makes the sorting process lighter.
• Optimized joins: Setting it on columns used for relationships makes data linking smoother.

Many databases maintain indexes in a tree-like structure called a B-Tree.

What is a B-Tree?

In a state without an index, you have no choice but to search by flipping through pages starting from the first one. However, with a B-tree, you can narrow down the location of the target data in just a few steps.

Search Process for 14 Using a B-tree

1. Starting point: Root node. First, look at the top node. Here, there is the number 12.

2. The 14 you are looking for is larger than 12.
   Based on this comparison, the B-tree decides to proceed to the right node and moves to the next level.

3. To the next internal node: The node to the right contains the number 15.
   Now, the 14 you are looking for is smaller than 15.
   Based on this comparison, the B-tree decides to proceed to the left node and moves down another level.

4. Destination: Arrived at a leaf node ⭕️ Looking at the node reached by going left (the green box), the node reached by going left (the green box) contains 14, and we have successfully found the target data.

As you can see from this sequence, a B-tree can ignore irrelevant data.
Once compared with 12, there is no need to check nodes like 3, 1, or 9 located on its left.
Additionally, the search range is significantly narrowed down through comparisons at each node.

For Example?

Prisma example

model Item {
  id    Int    @id @default(autoincrement())
  name  String
  price Int

  @@index([name]) // Create an index on the name column
}

For example, suppose you issue a query to search for a product where the name is "Apple".

Without an index (Full Table Scan), the database checks from the first row of the table in order, asking "Is this an 'Apple'?" until the end. If there are 1 million records, it could potentially check 1 million times. 🏃‍♂️💨

With an index (B-tree search), you follow a tree arranged in alphabetical order, as shown in the previous diagram.

"Is it before or after 'M'?" → "Before (Go left)", "Is it before or after 'F'?" → "After (Go right)"—and in just a few steps, you reach the location of "Apple".

Considerations

• Slower Writes
  Every time a single piece of data is added, the database needs to perform an addition to the index as well as the write to the main table. Since more indexes mean more update locations, applying too many indexes to a table with frequent writes can actually make it slower.

• Index Fragmentation and Bloating
  When deletions and updates are repeated, empty spaces can appear within the index pages, or unnecessary entries may remain, which apparently can reduce search efficiency. It seems that periodic maintenance is necessary in such cases.