B-Trees and Database Indexes

I realized after a few years of doing it that my strategy for keeping Wikis useful is to treat them as B-Trees.<p>When the landing page gets too full&#x2F;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.<p>Similar and older links get pushed down into the sibling that best represents the topic. Then if the destination page is now too big, similar and older links get pushed down to their children. Eventually all of the outdated docs are three levels down from the landing page, where only historians and experts will see them. And sometimes as we finally decide how part of the system really should work, siblings get combined into one page, minus the speculative work that gets pushed down deeper in the tree. It works remarkably well. At the end of the day documentation is a search problem.<p>I highly recommend it for a Friday afternoon exercise when you want to be productive but you know starting a new task is a complete waste of time.

Thanks for the amazing visual, Me and my team had worked on BTree+ indexing support on the top of Aerospike as we have different huge data sets 5T of data and each data set belong to an X property which suppose to have its own order table indexing.<p>The challenging part was evicting the expired keys from the BTree+ where the inserted keys would have TTL therefore we decided to fuse only one level branch and within the first sibling leaf nodes as it would be expensive if we perform clean up all the way up which would cause high lock contention and slow things down substantially specially when keys get inserted&#x2F;deleted&#x2F;updated.<p>Also we had to do sharding on top of the BTree+ to speed things up and reduce the high lock contention, that way we know what shard the the keys belong to and we lock the branch before performing any CUD, That way we can perform high concurrent operations on multiple shards&#x2F;branches.<p>The clean up process might have some caveat and the Btree+ ends up unbalanced. We had to provide rebuild indexing feature so that would fix all the gaps if necessary to avoid extra clean up operations.<p>Again Thanks for the visuals.

This is why you should _never_ make your UUID column the primary key.<p>For one, it&#x27;s enormous. Now you have to copy that 128bit int to every side of the relation.<p>Two, in most cases it&#x27;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.<p>Use regular bigserial (64bit) PKs for internal table relations and UUIDs (128bit) for application-level identifiers and natural keys. Your database will be very happy!

The cookie modal doesn&#x27;t work on Firefox mobile and it takes half the height.<p>Why don&#x27;t let the user set that up on their browser

beautiful interactive visualizations, this is top shelf in terms of pedagogy and vulgarization

I have been looking for something like this for so long, amazing post. I would love a section on composite indexes. That is something that I still have a hard visualizing…

Awesome article!<p>I only wished that the reference to InnoDB storing data in the B tree itself is otherwise referred to as a clustered index.<p>MyISAM before it was non-clustered.<p>Oracle and others let you choose.

great piece of education. The interactive demos like these help a lot.

If our disk block and B-tree node is 16k, and our keys, values, and child pointers are all 8 bits, this means we could store 682 key&#x2F;values with 683 child pointers per node. A three level tree could store over 300 million key&#x2F;value pairs (682 × 682 × 682 = 317,214,568). —— Should be 8 bytes per element?

may I ask what the v0, v1, ...v10 mean in those graphs? different pages?