Index - Btree structure (Balanced Tree)

Data System Architecture


B*Tree indexes :

  • has a tree structure
  • provides fast access, by key, to an individual row or range of rows
  • normally requiring few reads to find the correct row
  • are similar in implementation to a binary search tree
  • there is a one-to-one relationship between an index entry and a row: an entry points to a row. Not the case of Relation - Bitmap Indexes.

B in B*tree does not stand for binary but rather for balanced.

The index records are stored in the leaf pages of the tree.


The lowest level blocks in the tree, called leaf nodes or leaf blocks, contain every indexed key and a rowid that points to the row it is indexing. The interior blocks, above the leaf nodes are known as branch blocks. They are used to navigate through the structure.

That makes satisfying a predicate, such as the followings, pretty simple :

  • where x between 20 and 30
  • where x = 30

All leaf blocks should be at the same level.

Discover More
Data System Architecture
Index - Btree (When Should You use it)

When you should we use a btree index. Rule of thumb if you're going to access a very small percentage of the rows in the table via the index if you are going to process many rows of a table and...
Data System Architecture
Index - Performance

The impact of index on performance can be resumed as: Too many indexes and the performance of DML will suffer. Too few indexes and the performance of queries (including inserts, updates, and deletes)...
Card Puncher Data Processing
MySql - Index

innodb index - Doc - Accessing a row through the clustered index is fast because the index search leads directly to the page with all the...
Card Puncher Data Processing
Oracle Database - (B|Balanced) Tree - BTree indexes

The implementation of btree index in the Oracle database. To get to the leaf block to retrieve the first row of a query of the form will take the same number of I/Os regardless of the...
Data System Architecture
Relation - Bitmap Indexes

Normally in a btree, there is a one-to-one relationship between an index entry and a row: an entry points to a row. Indexes should be selective in general. With Bitmap Indexes, a single entry uses a bitmap...
Data System Architecture
Relation - Index (Indices)

An index is an auxiliary data structure of a relation database to speed up the retrieval of rows. Indexing the data can lead to either performance or degradation of queries, so understanding indexing...
Data System Architecture
SQL - Query Performance

The query performance is the of a query. OLTP query are query that comes from an OLTP application. This kind of query retrieve few rows and their performance is generally improved with a index....
Text Mining
What are models of text in NLP? (Natural Language, Text Modeling)

This page talks model creation for natural language text. ie how to store and represent text ? Let's say that you want to search in a list of documents, documents that are similar on 2 dimensions,...
Data System Architecture
What is a Key Value Database/Store?

A key-value database / store is a NoSQL database based on the key-value data that is stored in btree or map data structure. You store some data, called a value, inside a key. The data can later be...

Share this page:
Follow us:
Task Runner