Suggest an editImprove this articleRefine the answer for “What does the term "index tree" mean?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)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), where data is sorted by key and lookups go from the root down to the leaves. **Key point:** an index tree's advantage is **O(log n)** search complexity instead of **O(n)** without an index, efficient inserts and deletes without a full rebuild, and data that stays sorted, which speeds up `ORDER BY` and range queries.Shown above the full answer for quick recall.Answer (EN)ImageAn 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**.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.