I live mostly in the front end world, but if I was asked this (without looking it up) I'd say a DB builds a tree (balanced tree, binary tree maybe?) using the columns requested. This allows for very fast lookups when the table is queried for its indexed column(s), and blows away the worst case scenario of a non-indexed query time wise, where the DB has to do a full table scan to find out that a record doesn't exist. The trade-off is that the index must be rebuilt on inserts (probably deletes and maybe updates too?) and the resulting data structure stored, which is why you don't just index all the things.