Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

B-Trees and Database Indexes

planetscale.com

Post reply on HN
Print view View original

21–30 of 84 posts

Re: B-Trees and Database Indexes

#21

Post by benwilber0 »

paulryanrogers wrote: post #20
benwilber0 wrote: post #19

This is why you should _never_ make your UUID column the primary key. For one, it's enormous. Now you have to copy that 128bit int to every side of the relation. Two, in most cases it's completely random. Unless you had the forethought to use something other than UUIDv4 (gen_random_uuid). So now you just have a bunch of humongous random numbers clogging up your indexes and duplicated everywhere for no good reason. Us…

Won't you still need indexes on those UUIDs anyway? And possibly have to do more joins to resolve them?

You only need 1 index on the UUID. Instead of everywhere the UUID is referenced from other tables

Re: B-Trees and Database Indexes

#22

Post by Sophistifunk »

benwilber0 wrote: post #19

This is why you should _never_ make your UUID column the primary key. For one, it's enormous. Now you have to copy that 128bit int to every side of the relation. Two, in most cases it's completely random. Unless you had the forethought to use something other than UUIDv4 (gen_random_uuid). So now you just have a bunch of humongous random numbers clogging up your indexes and duplicated everywhere for no good reason. Us…

It's very interesting to me that we have to keep telling people this, but it hasn't become part of the "hive folk knowledge" we all seem to develop. I think DB vendors have been sleeping on an opportunity to encourage better practices.

Re: B-Trees and Database Indexes

#23

Post by thesz »

benwilber0 wrote: post #19

This is why you should _never_ make your UUID column the primary key. For one, it's enormous. Now you have to copy that 128bit int to every side of the relation. Two, in most cases it's completely random. Unless you had the forethought to use something other than UUIDv4 (gen_random_uuid). So now you just have a bunch of humongous random numbers clogging up your indexes and duplicated everywhere for no good reason. Us…

If you sort UUIDs, there will be a lot of common prefixes. B-trees implicitly sort data so you can factor common prefix from all keys of B-tree page.

But!

UUIDs are random and B-tree will have increased fragmentation after a short while.

I once tried to insert a puny 1 million scale free graph edges into a B-tree (BerkeleyDB) in 1K batches and it failed miserably - I've waited for an hour and then killed it. LSM trees were an orders of magnitude faster at 100K edges, so BDB had shown that B-trees are no match there.

B-trees are semi-static data structures, they are hard to rebuild incrementally if data is random. But they shine if input keys are sorted.

Use UUIDs as you like to use them if your storage engine is LSM tree. Use staged sorting (LSM tree in disguise) if you ue B-tree.

Re: B-Trees and Database Indexes

#24

Post by paxys »

Sophistifunk wrote: post #22
benwilber0 wrote: post #19

This is why you should _never_ make your UUID column the primary key. For one, it's enormous. Now you have to copy that 128bit int to every side of the relation. Two, in most cases it's completely random. Unless you had the forethought to use something other than UUIDv4 (gen_random_uuid). So now you just have a bunch of humongous random numbers clogging up your indexes and duplicated everywhere for no good reason. Us…

It's very interesting to me that we have to keep telling people this, but it hasn't become part of the "hive folk knowledge" we all seem to develop. I think DB vendors have been sleeping on an opportunity to encourage better practices.

DB vendors haven't done enough to offer ID generation as a core part of their system. Ideally "what ID do I use for this object" shouldn't even be a consideration, because of course the database should handle it. It is the system of record after all. Yet your options are pretty much limited to UUID or a basic incremental counter that fails to meet any real world production constraints.

Re: B-Trees and Database Indexes

#25

Post by wbsun »

benwilber0 wrote: post #19

This is why you should _never_ make your UUID column the primary key. For one, it's enormous. Now you have to copy that 128bit int to every side of the relation. Two, in most cases it's completely random. Unless you had the forethought to use something other than UUIDv4 (gen_random_uuid). So now you just have a bunch of humongous random numbers clogging up your indexes and duplicated everywhere for no good reason. Us…

Isn’t there also hash based index for random keys?

Re: B-Trees and Database Indexes

#26

Post by sroussey »

Awesome article!

I only wished that the reference to InnoDB storing data in the B tree itself is otherwise referred to as a clustered index.

MyISAM before it was non-clustered.

Oracle and others let you choose.

Re: B-Trees and Database Indexes

#27

Post by shnock »

caseyohara wrote: post #10
hinkley wrote: post #8

I realized after a few years of doing it that my strategy for keeping Wikis useful is to treat them as B-Trees. When the landing page gets too full/too many outgoing links, I start pushing links and paragraphs down into the child pages, to leave space for a fair share of timely links and on-boarding docs. Similar and older links get pushed down into the sibling that best represents the topic. Then if the destination…

Do you have a recommendation for Wiki software you like to use? My team is in need of an internal knowledge base, and I like the structure of wikis. Most of the SaaS products I've tried or looked at are a bit too shiny/fancy and don't seem to match my mental model of how a wiki-style knowledge base should work.

Confluence, but we're already in deep w Atlassian

Re: B-Trees and Database Indexes

#28

Post by benwilber0 »

wbsun wrote: post #25
benwilber0 wrote: post #19

This is why you should _never_ make your UUID column the primary key. For one, it's enormous. Now you have to copy that 128bit int to every side of the relation. Two, in most cases it's completely random. Unless you had the forethought to use something other than UUIDv4 (gen_random_uuid). So now you just have a bunch of humongous random numbers clogging up your indexes and duplicated everywhere for no good reason. Us…

Isn’t there also hash based index for random keys?

Maybe? idk. Not in Postgres. The default index is a B-Tree. A hash-based index would be terrible for disk-seeking, in any case.
Post reply on HN