How does database indexing work? (2008)

Take a large unordered text file and then create an ordered index in a separate file of word ==> line

write a brief binary search algo to search the index.

Compare searching the words with a "table scan" on the first file using grep, vs the binary search on the index.

You will find the table scan is O(n) and your binary search is roughly O(log n)

In 60 minutes you'll understand more about indexing than reading stack overflow.

Honest answer: If the blocks aren't* contiguous, there's an index for that!

(* 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.

disk block # = f(index) can be implemented with a b-tree but it can also be implemented (in some cases) with a deep-learning based approach.

I think that advice is not necessarily correct.

Suppose you have this query:

    select a, b
    from T
    where x = 1

And suppose you have an index on x. You can locate the x=1 INDEX records using the index quickly (probably no more than 1-3 disk accesses). But then the qualifying TABLE records have to be retrieved. That index lookup could turn up thousands of qualifying records, and now you have to retrieve each record to get the a, b values.

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's not, because in a standard B-tree all the leaf nodes are at exactly the same depth, whereas in a binary tree they are not in general, unless the binary tree is balanced with exactly 2N leaves.

This difference occurs because a B-tree can have interior nodes that aren't completely full, whereas a binary tree's interior nodes have exactly 2 children.