The labs on this site need JavaScript to run. The same content is written out below.

Learn › Database › Indexes and execution plans

Binary search and B-trees

If the data is sorted, you can discard half at a time

You look for one value among 27 values. You can check them one by one from the start. If they are sorted, you can look at the middle and discard half. Or you can use a B-tree, which splits the search into many branches at once.

Checked against real execution · The search on the screen is the result of actually running the algorithms

Concepts in this lab

Binary search

This search method works on sorted data: it compares the target with the middle value and cuts the search range in half each time. Its time complexity is O(log n). It can be used only when the data is sorted. A B-tree index in a database uses the same principle of narrowing the range over sorted data.

Time complexity (big-O notation)

This notation shows how fast the number of operations of an algorithm grows as the input size n grows. O(1) means constant regardless of size, O(log n) means only one more step when the size doubles, O(n) means proportional to the size, and O(n²) means proportional to the square of the size. It is the basis for judging which approach holds up as the amount of data grows.

B-tree index

The index structure that most relational databases use by default. It is a balanced tree that keeps values sorted, and each node holds many keys, so the height of the tree is low. You can find a value by going down only a few levels from the root. Because the values are sorted, it is used not only for equality lookups but also for range lookups and sorting.

Full table scan

A way of finding the rows that match a condition by reading every row of the table from beginning to end. It is chosen when no index can be used for the condition, or when an index exists but the optimizer judges that reading everything is better because too many rows match the condition. When it is used to find a few rows in a large table, it causes performance problems.

Index

A data structure that keeps the values of specific columns separately, in sorted form, so that the wanted rows of a table can be found quickly. Without one, the whole table must be read to find the rows that match a condition. Reads get faster, but it must also be updated every time data is inserted, updated, or deleted, so it costs write performance and storage space.

Try these

• Default settings — One by one from the start. It checks 23 times to reach a value near the end.
• With binary search — It finds the same value in 5 checks.
• With a B-tree — It reads only 3 nodes to find any value.
• Looking for a missing value one by one — It has to check to the very end to know the value is not there.
• A missing value with a B-tree — It confirms the value is not there with 3 nodes too.
• With 1 billion rows — See the difference in the number of steps by method in the table below.

Running with the default settings

1. The 27 values are piled up unsorted (on the screen they are shown in order of size to make them easier to read). There is nothing to tell where the value is, so you check the values one by one from the start.
2. Check #1: 10 → No. Move to the next slot.
3. Check #2: 20 → No. Move to the next slot.
4. Check #6: 60 → No. Move to the next slot.
5. Check #12: 120 → No. Move to the next slot.
6. Check #18: 180 → No. Move to the next slot.
7. Check #23: 230 → Found.

Result of this run

• Checking one by one takes 10 times as many checks when the data is 10 times as large (O(n)). To find out that a value is missing, you have to look at all of them. This is what the database does when you query by a column that has no index.
• The difference among the three methods is "whether the data is kept sorted" and "how much is discarded at a time". A database index keeps the values sorted and stored in a B-tree, and the price is that the tree must be updated every time you insert or change a value.

Code

// If the data is not sorted, the only way is to check everything from the start
for (int i = 0; i < rows.length; i++) {
    if (rows[i] == target) return i;
}
return -1;                              // you know it is missing only after checking to the end

-- In a database, this is the same as searching by a column that has no index (full table scan)
SELECT * FROM orders WHERE amount = 230;

Assumptions of this model

The search steps and counts for 27 rows are the result of this page actually running the algorithms. The counts for large numbers of rows are the maximum number of steps, calculated from "how many branches the search splits into at a time". The B-tree on the screen has the shape in which the values are only in the leaf nodes (a B+tree), and the index of MySQL InnoDB has this structure. How many values fit in one node of a real index depends on the size of the key, and 500 is just an example value. The root and internal nodes are usually already in memory, so the number of real disk reads is smaller.

Previous lab: Views, stored procedures, and triggers · Next lab: Indexes and full table scans