Do I understand indexes correctly?

Question

I'm trying to wrap my head around the difference between various kinds of database indexes. I have created a little example for myself and I don't know whether I'm understanding everything correctly.

Let's say we have an fictional database table like this:

addr col1  col2
===============
1    a     b
2    c     b
3    a     c
4    d     d
5    c     a
6    a     b
7    c     b
8    d     d
9    a     c

addr here is a physical location of the corresponding tuple. Here is my understanding of how a single-column, a multi-column and a covering index would look like (not physically, rather on a conceptual level):

create index on col1
a - 1, 3, 6, 9
c - 2, 5, 7
d - 4, 8

create index on (col1, col2)
a b - 1, 6
a c - 3, 9
c a - 5
c b - 2, 7
d d - 4, 8

create index on col1 include col2
a - 1b, 3c, 6b, 9c
c - 2b, 5a, 7b
d - 4d, 8d

So my question is: do I get it right?

Answer 1

You're pretty much right but this isn't the best way to conceptualize it, rather you should draw out a Tree since that is the logical data structure typically used to hold the data within an index.

Using your notation, your first example and your third example are a little hard to distinguish between what is meant to be the key / row ID for referencing the actual row and what is the included field (but I understand what you mean, given your schema details).

Here is a good article on indexing and B-Trees which has a good example of how to conceptualize it. (You can ignore the database system specific comments, such as the section on SQLite, as the generals in this article apply to pretty much any modern relational database management system.) Additionally you can play around with this B-Tree simulator to help you visualize how they grow as data is added to an indexed table.

Answer 2

You are not far off the mark. My biggest complaint is that if there are several identical index keys, you will have several index entries. What you depicted looks more like a GIN index (except GIN multi-column indexes are different).

The actual implementation of an index is a tree structure, but you lose nothing if you imagine it as an ordered list.

So I would portray the indexes like this:

CREATE INDEX ON tab (col1);

key	address
a	1
a	3
a	6
a	9
c	2
c	5
c	7
d	4
d	8

For equal keys, the entries will be sorted by address from PostgreSQL v12 on. In older versions, the order was arbitrary.

CREATE INDEX ON tab (col1, col2);

key	address
a, b	1
a, b	6
a, c	3
a, c	9
c, a	5
c, b	2
c, b	7
d, d	4
d, d	8

CREATE INDEX ON tab (col1) INCLUDE (col2);

key	address
a (b)	1
a (c)	3
a (b)	6
a (c)	9
c (b)	2
c (a)	5
c (b)	7
d (d)	4
d (d)	8

The included column will only be in leaf pages of the index, and the index doesn't care about its ordering.