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.

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

Explanation

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.

Explore the dry run

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

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}.

Java: an ordered index with TreeMap

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading