Java · Course navigation

Java: an ordered index with TreeMap

Use a sorted map the way a database uses an ordered index to answer range and nearest-key queries.

On this page

Before you start

Java Map basics.

Use a sorted map the way a database uses an ordered index to answer range and nearest-key queries.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A database index maps a column value to the rows that hold it. A hash index answers exact lookups quickly but cannot answer range queries such as ages between 25 and 40. An ordered index, usually a B-tree, keeps keys sorted and supports both.

TreeMap is a sorted map built on a balanced tree, so it keeps its keys in order and each operation takes O(log n). firstKey and lastKey give the minimum and maximum, subMap returns a range, and floorKey and ceilingKey find the nearest keys below and above a value. TreeMap itself is an in-memory tree, not a B-tree, but it behaves like an ordered index.

Code example

Java

import java.util.*;

class Main {
  public static void main(String[] args) {
    TreeMap<Integer, String> byAge = new TreeMap<>();
    byAge.put(31, "Cy");
    byAge.put(24, "Ada");
    byAge.put(45, "Di");
    byAge.put(29, "Bo");

    System.out.println(byAge.firstKey() + " " + byAge.lastKey());
    System.out.println(byAge.subMap(25, true, 40, true));
    System.out.println(byAge.floorKey(30) + " " + byAge.ceilingKey(30));
  }
}

Output

24 45
{29=Bo, 31=Cy}
29 31

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1import java.util.*;

3class Main {

4 public static void main(String[] args) {

5 TreeMap<Integer, String> byAge = new TreeMap<>();

6 byAge.put(31, "Cy");

7 byAge.put(24, "Ada");

8 byAge.put(45, "Di");

9 byAge.put(29, "Bo");

11 System.out.println(byAge.firstKey() + " " + byAge.lastKey());

12 System.out.println(byAge.subMap(25, true, 40, true));

13 System.out.println(byAge.floorKey(30) + " " + byAge.ceilingKey(30));

14 }

15}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The four keys are kept in sorted order: 24, 29, 31, 45.	`keys = 24, 29, 31, 45`	—
The smallest and largest keys are at the ends of the tree.	`keys = 24, 29, 31, 45`	24 45
A range query: ages from 25 through 40.	`keys = 24, 29, 31, 45`	24 45 {29=Bo, 31=Cy}
The nearest key at or below 30 is 29; the nearest at or above is 31.	`keys = 24, 29, 31, 45`	24 45 {29=Bo, 31=Cy} 29 31

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

Cost and common mistakes

put, get, floorKey, and ceilingKey are O(log n); a range query costs O(log n + k) for k results.

TreeMap needs keys that are comparable. Mixing incomparable types throws ClassCastException.
A TreeMap holds one value per key. A non-unique index must map each key to a list of rows.

Try it yourself

Which keys does byAge.headMap(30) contain?

Reveal answer and reasoning

It holds the keys strictly below 30: {24=Ada, 29=Bo}.