CSE Roadmap

Core tier · about 3 hours · 5 parts

Part 1 of 5 · 1 min read

Why this page comes first

In this module you will

  • Explain what makes a B+-tree an ordered index, and why that supports range queries.
  • Describe the structure of a B+-tree: internal nodes, leaf nodes, and the linked leaf chain.
  • Trace what happens to a B+-tree when a leaf node fills up and splits.
  • Explain why a B+-tree stays balanced as rows are inserted over time.

The previous page described a generic search tree sitting above leaf nodes. The B+-tree is, by far, the most common real implementation of that idea, used as the default index structure in most relational databases. This page gives it the depth it deserves.