How does database indexing work? (2008)

Lol

Binary trees are the ideal in a world of a pure von Neumann model. In practice data structures perform better when data is grouped together and this is what the b-tree gets you. It's both more disk and cache efficient in real world workflows

EDIT: This is no longer true. Thanks latch!

As of 14.1, they still don't support unique constraints:

   select amname, pg_indexam_has_property(oid, 'can_unique') from pg_am

   amname | pg_indexam_has_property 
    --------+-------------------------
     heap   | ¤
     btree  | t
     hash   | f
     gist   | f
     gin    | f
     spgist | f
     brin   | f

For sorting or adjacency queries, you want a btree index. A hash index can give you O(1) lookup with the drawback that you lose ordering completely (whereas getting a sorted selection of records with a tree is a O(1) operation). The trick here is having a hashing function which is both fast and avoids collisions (the worst case scenario is hash(x)=1 where everything hashes to the same value and you end up again with O(n) lookups).

They are just SELECTed, i.e. sent in the output (the query results).

Suppose you have this query:

    select a, b
    from T
    where x = 1

Now suppose that you replace your index on (x) with an index keyed by (x, a, b). You can still search for x=1 using this index, but now, the (a, b) values that you are SELECTing are present in the index itself. You don't have get the table records to get those values. That can save a lot of random accesses, and there are secondary effects, since the pages containing those records aren't brought into the disk cache.

Yes, this wider index has space and update costs, but the benefit is often worth it.

(* It depends on the database type. In an LSM-tree layer, the blocks are typically contiguous in a file, so direct binary search is possible, though it might not be the most efficient method. The filesystem handles locating blocks in this case.)

The database table is disk blocks containing data where the blocks are logically in order of keys, as if in a contiguous array. Really they are laid out differently on disk.

So there's a block index, which is just a smaller version of the same table data structure: a table mapping keys to values, implemented as blocks in logical order of keys, as if in a contiguous array. Except in this index, the map is from key-ranges of the first table to block locations on disk. This index lets you go from keys to block locations on disk, and it also lets you do a course-grained version of the binary search to narrow down to a single block of the larger table.

Ok, but then how do you look things up in the block index if it's using the same kind of data structure, made of multiple blocks? Same again: Each block index has its own smaller block index.

This neat recursive definition gives you a tower of progressively smaller block indexes until the size is just one block, which doesn't need an index.

Guess what you get when each table of logically sorted, contiguous blocks has a smaller index to say where the blocks are really located?

The data structure is called a B-tree (technically a B+tree), and the smallest index is the root block.

The tree structure arises from the recursive description, where each table has another table (until it stops).

This is a decidedly non-standard way of describing the B-tree data structure. There's no explicit tree. But it's a valid and useful alternative view. (Note, these block indexes are not what is generally meant by database indexes, and they are not visible at the SQL level. They are an implementation detail.)

One of the useful things to emerge from this view is that each level is just logically a flat table, made of blocks that are logically in key order but have arbitrary physical location. It's not necessary for every index to use the same data structure, or be on the same storage. Depending on how you think about algorithms, this description might be simpler to work with.

He also wrote the other question that he links to, How to index a database column, with the request to get answers for each major type of database. So he's asking not so much to learn the answer but to provide a place for others to provide a catalog of answers.

This is different of course from the case where someone asks a genuine question then comes back and writes an answer to themselves when they have learned it. This happens a lot too.

Yep, that old :(

Additionally, parent’s answer doesn’t actually answer the question, by saying what an index is, but the question was “how does it work?” The top SO answer does a great job with this one, I think. Another one a few answer down also goes into some of the downsides (it slows down writes, for one). The whole page is worth a skim if you’re not a DBA but have to fiddle with DBs on occasion.

1. Binary search. It's be really handy to have the URLs stored in a different order, maybe grouped by client_id first and then all the URLs for the same client are alphabetical. The index conceptually just contains the same rows in a different order.

2. The read vs write trade-off. Your data fits in memory if there's less than 10 TB of it (possibly up to 100 TB) so the big thing is latency, what an index does is, it requires you to write the same information twice in order to read it exponentially faster, so depending on how often do you write versus how often you read, indexes make less or more sense.

3. High fan-out trees. Once you have explained that the index is just an the same data in a different order, you have inserted a sort of ticking time bomb of misunderstanding. The problem is, a beginner programmer’s notion of a freely indexable list, such that binary search works on it, is an array. How do we insert into an array? With all the work of array copies! So you get people who think that random ID columns should never be indexed, because every write into the middle of the array has to shove half the data one cell to the right—unacceptable! So it really helps to say, “now we can store this as a binary tree, make one comparison per level of the tree.” Pause for understanding that the “list,” can be stored with such a tree. “but, modern computers have a nice property that right after accessing some memory the memory near that location is loaded into a cache... this makes arrays real fast. Suppose we don't just have the binary tree thing of 2 child nodes each representing 50% of our data, but an array with 100 pointers each representing 1% of the data, you get something like a 6x memory speedup from the cache, because your tree is one sixth the depth of the binary tree. And that's basically what a B-tree is, you use a higher fan-out of your sort tree to exploit the cache.”