Indexing in PostgreSQL is completely programmable. It's straightforward (albeit not quite easy) to create a totally custom index type, even with customized operators for how to compare values. A few unusual index types are included with the core database.
Index types
B-tree
The standard index type is the B-tree, where the B stands for balanced. A balanced tree is one where the amount of data on the left and right side of each split is kept even, so that the amount of levels you have to descend to reach any individual row is approximately equal.
The B-tree can be used to find a single value or to scan a range, searching for key values that are greater than, less than, and/or equal to some value. They also work fine on...