Suggest an editImprove this articleRefine the answer for “What does "B-tree index structure" mean?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)B-tree is the standard index structure type in a DBMS that allows search, insert, and delete in logarithmic time O(log n): it keeps keys sorted in a self-balancing tree (usually 2-4 levels even with millions of rows) and lets you quickly find the range of values you need. **Key point:** B-tree is ideal for `WHERE column = X`, ranges, `ORDER BY`, and `JOIN`s on indexed keys, but it's a poor fit for `LIKE '%text'` with a leading wildcard - that needs other index types (GIN, GiST, FTS).Shown above the full answer for quick recall.Answer (EN)ImageB-tree is the standard index structure type in a DBMS, letting search, insert, and delete run in **logarithmic time O(log n)**. It's used in PostgreSQL, MySQL (InnoDB), Oracle, and others. Its job is to keep keys sorted and let you quickly find the range of values you need. To the point, without the padding, at a middle level: ### 1. What B-tree means in the context of an index It's a **balanced tree-shaped store**, in which: - every node holds **sorted keys** - nodes hold **references to child nodes** - the tree is **always balanced by height** (usually 2-4 levels even with millions of rows) - the leaves hold references to the table's physical rows (or the data itself, depending on the implementation) ### 2. How B-tree speeds up search The search algorithm works like a phone directory: - the DB starts at the root - based on the keys inside a node, it figures out which "child" to descend into - it repeats the step until it reaches a leaf - it gets the row's address without scanning the whole table Instead of `N` comparisons, it's **~log₂(N)**. At large volumes the difference is huge: instead of 1,000,000 comparisons, around 20. ### 3. Why B-tree specifically, and not a plain binary tree Because a plain search tree can easily "collapse" into a line and degrade to O(n). B-tree **strictly enforces balance**, so its efficiency is stable and predictable. ### 4. What kinds of queries B-tree is ideal for - `WHERE column = X` - ranges: `BETWEEN`, `>`, `<` - `ORDER BY`, if the order matches the index - `JOIN`s on indexed keys ### 5. An important nuance B-tree is a **poor fit** for `LIKE '%text'` (a leading wildcard), because that kind of query can't be searched by sort order, it needs a full scan or other index types (GIN, GiST, FTS). ### Summary B-tree is a self-balancing index structure that keeps keys sorted and lets you search for values in O(log n), so queries by condition, range, sorting, and joins run fast regardless of the table's size. If you'd like, I can draw a B-tree in my next message using a real index example and walk through, step by step, how `WHERE value = 42` happens at the node level.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.