Belongs to /DB theory
Background
A table like this is stored in a heap file by Postgres or any other SQL DB.
| id | name | subbed |
|---|---|---|
| 1 | Max | true |
| 2 | Tim | false |
| 3 | Carla | true |
This heap file contains multiple blocks. Each of these blocks is usually 8 kb in size. When the table grows, as more records are stored, the records spread over multiple blocks. Doing a full-table can dues includes multiple blocks, but the jumps between the blocks are slow, thus getting all the values from a column with many entries can be slow.
An index holds points to the block of some data. They are allocated to columns of a table.
Balanced trees and indexes
Commonly, b+ trees are used to hold the pointers to the blocks, as they are an efficient structure for searching.
Cons of indexes
- Indexes require a lot of space
- Inserting, updating and deleting some data also requires the indexes to update
Creating indexes
CREATE INDEX idx_username ON users(username);
That’s it.