What is a database index really?

[Mike Austin]

Sometimes I like to go back to the start. When I create a database index, I know what it does, it's just a reverse lookup. But coding it, you see how unique indexes can be different from non-unique indexes.

Postgres has "index de-duplication", but it happens lazily and wasn't added until version 13. I see at least two types of index but they don't need to be done lazily:

PrimaryIndex<uint64_t, 4> itemIdPrimaryIndex = {

    { 2000, 2001, 2002, 2003 }, // item id
    { 0, 32, 72, 120 }, // storage offset
};

SecondaryIndex<uint64_t, 3, 4> itemTeamIdSecondaryIndex = {
    { 100, 101 }, // team id
    { 0, 2, 4 }, // index into first matching key (with end of range index)
    { 32, 0, 120, 72 }, // storage offset, secondarily sorted by updated_date

};

So now I should be able to get all items by team, sorted by updated_date, all in one index. Again nothing enlightening, rather obvious, but it's fun to go bare bones to really think about something. The structs of array vs array of structs is for SIMD and cache optimization.

Postgres also has a "covering index" where you can stuff data in the index node. Maybe good for small things but it will bloat your index, and B-Tree pages are only 4K or so.

Conditional indexes are interesting, because if you're only interested in one team for example, you can just index on that and the it will not index teams.

[Mike Austin]

I keep reading MySQL clustered index make finding primary keys fast - the table itself is a b-tree index by primary key with the data inside the "index". This kept me thinking - for small rows maybe it's ok, but with large rows you're going to need to pull in so much data *just to find the one record*. Don't drink the lemonade. Also reorganizing the actual database on inserts (less if incremental key) seems heavy vs Postgres using a heap (just a bunch of unsorted records). Retroactively sorting the heap would be helpful for keeping things like "tenant_id" tenants or "team_id" physically closer together.

https://www.google.com/search?q=mysql+clustered+index+not+performant+with+large+records