7 ms·
B-Trees and Database Indexes
- deleted 2y ago[deleted]
- VeejayRampay 2y agobeautiful interactive visualizations, this is top shelf in terms of pedagogy and vulgarization
- bddicken 2y agoThat's the goal! Thanks for the kind words.
- eclectic29 2y agoSlightly off topic: Learnt a new word today 'vulgarization' which seems to have a completely different meaning from the obvious. Thanks.
- egwynn 2y agoNote that, in the abstract, “vulgar” means “common” (as in “vulgar latin”). Indeed, its negative connotations come from that same sense: “common” people are unrefined.
- hinkley 2y agoThe association between vulgarity and propriety (and class distinctions) sort of ruins that word, particularly in the english speaking west. I wonder if that's as big of a problem in the romance languages (which all treat left/right the same way - left = bad, right = good)
- jjgreen 2y agoIndeed: are you sinister or dexterous?
- hinkley 2y agoIn French the same word for “right” means the same notion in English for - direction - straight ahead - civics - propriety
- nickpeterson 2y agoAs a left-handed contrarian, I’ve always enjoyed that sinister and left handed go hand in hand.
- LtdJorge 2y agoYes, in Spanish vulgar is used as inappropriate. We have "el vulgo" (el pueblo, the people), which kinda teaches you the correct meaning, popular, unrefined. But "vulgo" is seldomly used.
- egwynn 2y agoThis goes pretty deep in English. I'd argue that the semantic intention behind the colloquial usage of "vulgar" is nearly inseparable from the "class distinction" baggage it carries. Consider these common synonyms and their etymologies: - Rude: "coarse, rough, unfinished, unlearned" (https://www.etymonline.com/word/rude#etymonline_v_16610 https://www.etymonline.com/word/rude#etymonline_v_16610) - Mean: "shared by all, common, general" (https://www.etymonline.com/word/mean#etymonline_v_12495 https://www.etymonline.com/word/mean#etymonline_v_12495) And even synonyms like obscene, indecent, or disgusting, which don't evoke this distinction directly, still almost always ultimately rely on separating things based on what is "good" and "clean" according to class distinctions.
- hinkley 2y agoI 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 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. 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.
- caseyohara 2y agoDo 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.
- shnock 2y agoConfluence, but we're already in deep w Atlassian
- hinkley 2y agoI don't think it really matters which you use. I've unfortunately been stuck in Atlassian for ages. But if you were shopping for one, from the standpoint of keeping the docs working being able see missing pages and see incoming links to a page are both pretty helpful. I kinda miss the latter.
- left-struck 2y agoIf you can self host, wiki.js is easy to set up in a docker container. Mediawiki (What Wikipedia runs on) is pretty easy too. If you have a small team, Obsidian and a syncing solution like git or obsidian sync might work. I was able to work with my company’s it team to set up a wiki which is only accessible from within the network, including by vpn, and is hosted on a vps.
- modriano 2y ago[flagged]
- samlambert 2y agothat's not meant to happen. we will fix.
- finnh 2y agowow! That was honestly even worse than you made it out to be.
- yosri-xp 2y agoThanks 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. 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/deleted/updated. 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/branches. 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. Again Thanks for the visuals.
- bddicken 2y agoYou're welcome! Sharding with B tree indexes... Hmmm, I know a company that does that.
- benwilber0 2y agoThis 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. 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!
- paulryanrogers 2y agoWon't you still need indexes on those UUIDs anyway? And possibly have to do more joins to resolve them?
- benwilber0 2y agoYou only need 1 index on the UUID. Instead of everywhere the UUID is referenced from other tables
- dspillett 2y ago> Won't you still need indexes on those UUIDs anyway? Depends on how index pages are structured in the DB. With MySQL (assuming the InnoDB engine) the primary key is pretty much always a clustered index, in MS SQL Server this is the case more often than not too. This means that any page expansion due to splits from the randomness of the data being inserted affects the whole table not just the key index, and rebuilding to claim back the wasted space later will take a lot longer as you are moving all your based data around. With the UUID as a supplementary key, likely indexed on its own, all that gets enlarged by excess page splitting is those 128-bit values not the entire rows and an index rebuild to fix that up after the fact moves a lot less data around. So yes, you have an extra index on top of your primary key and other additional ones needed by your apps and reports, but not having a random UUID as your clustering key can be a significant benefit. Using more ordered UUIDs minimises this difference considerably though. Even ignoring the random-key-causes-page-splits issue, if you've mitigated it with more ordered UUIDs, a wider primary key increases the size of all supplementary indexes assuming MySQL arranges things similarly to SQL Server: rather than having a hidden page/row identifier (as SQL Server does without any clustered key defined, it calls such arrangements heap tables), each supplementary index includes the clustering key value with every row. So while having a 32-bit primary key for internals and the 128-bit UUID as an extra key adds 4 bytes per row (for the extra INT32) to the base data, it saves 12 bytes from each row in each non-clustered index (as the INT32 is included, not the UUID). > And possibly have to do more joins to resolve them? Usually not. Usually when you have both the INT32 (or sometimes IN64) surrogate key is for all internal use and a UUID only for external references, so the UUIDs are only important as the initial filter and not likely not taking part in a JOIN at all. After the initial filter to find the item you want in the main table of the query, the JOINs to collect data from other tables will all be by the surrogate (INT) keys. The UUID is almost never used as a foreign key reference in this arrangement.
- sroussey 2y agoAwesome 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.
- bddicken 2y agoGood point! Yes, clustered index is one of the correct terms.
- is_true 2y agoThe cookie modal doesn't work on Firefox mobile and it takes half the height. Why don't let the user set that up on their browser
- IAmLiterallyAB 2y agoOr Chromium mobile
- vanderZwan 2y ago> it takes half the height. Ah so that's what the "planet scale" name refers to /j
- is_true 2y agoIt takes all the screen space from latitude 0° to -90°!!!
- handelaar 2y agoNor Chrome desktop
- crabmusket 2y agoIt has such an enticing "reject optional" button next to "accept all" and I was so impressed that they'd actually made the opt-out flow as easy as the opt-in flow... until I tried to use it. It's just maliciously incompetent at this point.
- bddicken 2y agoThe "reject all" button works better now, thanks for bringing this up.
- crabmusket 2y agoGreat to hear! Just checked it again on FF/Android and it works just how I'd have expected. Thanks for the update!
- dorbodwolf 2y agoIf 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/values with 683 child pointers per node. A three level tree could store over 300 million key/value pairs (682 × 682 × 682 = 317,214,568). —— Should be 8 bytes per element?
- spintin 2y ago[dead]
- misonic 2y agomay I ask what the v0, v1, ...v10 mean in those graphs? different pages?
- tnvmadhav 2y agogreat piece of education. The interactive demos like these help a lot.
- seanman 2y agoI 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…
- tpetry 2y agoI invented a new way of visualisi g composite ones when I wrote my book about indexing. You can scroll down on the landing page to the fundamentals chapter to see it. https://sqlfordevs.com/ebooks/indexing https://sqlfordevs.com/ebooks/indexing
- bddicken 2y agoThanks Sean! Yeah that would be very cool to have an interactive visual for that as well. So many possibilities!