What does the term "index tree" mean?

An index tree is the internal structure a database uses to store indexes for fast searching, inserting, and deleting data. The structure most commonly used is a B-tree (or its variants: B+-tree, B*-tree).

#The principle

• Data in the tree is sorted by key (e.g. id, email);
• Each node holds keys and references to child nodes;
• Lookups go from the root down to the leaves, each step getting closer to the target value.

#An analogy

Picture a phone directory:

• the letters A-Z are the "branches of the tree";
• inside each branch, names are sorted. When looking for "Smith", you don't scan the whole directory, you jump straight to the "S" section and then to the right page.

#Advantages of an index tree

• O(log n) search complexity (instead of O(n) without an index);
• efficient insert and delete operations without a full rebuild;
• data stays sorted, which speeds up ORDER BY and range queries (BETWEEN, >, <).

In modern DBMSes (PostgreSQL, MySQL, Oracle), almost all regular indexes are built on B-trees, because they strike a balance between speed and stability.