Lesson 4 of 11 · 24 min
B-tree indexes
By the end of this lesson you can explain how a B-tree index is organised, create one with CREATE INDEX, confirm in the plan that it is used (Index Scan, Index Only Scan or Bitmap scans), and list the operations a B-tree can speed up.
An index is a separate structure that stores the values of one or more columns in sorted order, each with a pointer to the row in the table. Think of the index at the back of a book: to find 'Riyadh' you don't read every page, you jump to R in the alphabetical list and follow the page number.
PostgreSQL's default index type is the B-tree (balanced tree). It has three kinds of pages:
- the root page at the top, holding a few keys that split the value range,
- internal pages below it, splitting each range further,
- leaf pages at the bottom, holding every key in order, each with a TID (tuple id: the page and position of the row in the table). Leaves are linked to their neighbours, so a range can be read by walking sideways.
To find a value, PostgreSQL reads the root, follows one pointer per level and lands on the right leaf. Because each page holds hundreds of keys, even millions of rows need only 3 or 4 levels: a lookup reads a handful of pages instead of the whole table.
This lesson, its 4 graded exercises and every other Members lesson in SQL Quest come with a Formula Quest membership that includes SQL (Single Quest with SQL selected, Quest Trio including SQL, or Quest Unlimited), or with SQL access from your organization.
Free to everyone: all of SQL Foundations and Retrieving and Filtering Data, the first lesson of every track, the playground, the dataset library and the SQL reference. See free lessons