B-Trees and Database Indexes
planetscale.com
planetscale.com
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.
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.
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.
I suspect this would be a good 'substitute' for documents that are often hosted on internal wikis.
[1]: https://github.com/oxidecomputer/rfd-site
[2] https://rfd.shared.oxide.computer/rfd/0001
[3]: https://oxide.computer/podcasts/oxide-and-friends/2065190
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.
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!
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.
One question is whether you do random or k-sorted UUIDs for a secondary key. K-sorted is likely faster, but in many cases the difference is small enough that you'd rather take the easy random route which is also guaranteed not to leak any info.
Replication should be fine, unless you mean active-active in which case I suggest a. not doing that b. using interleaved chunks, or a coordinator node that hands them out.
Business data exposure can be avoided (if it’s actually a problem, and not just a theoretical one) in a variety of ways; two of the most common are:
* Don’t use the id in the slug.
* Have a iid column that’s random and exposed, while keeping the integer as the PK.
If you need unique IDs across tables, then I question your use of an RDBMS, because you aren’t really making use of the relational aspect.
Converting int to bigint is not a big project, I have done more times than I can count just like any database evolution. I have also had customers say "oh, we'll just drop and recreate the table every year because its just some trash data." or "oh wait, we didnt mean to create 100 rows every second every day, that's a bug and costing us a lot of money for something we dont care about."
There's no one size fits all in databases, but most people who don't know better don't need to design a database for scale... because their choices won't work in the long term anyway.
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.
Beyond Postgres, indexing random values is fundamentally harder than indexing sorted ones, whether you've got a hashmap or btree or something else. The often-cited O(1) lookup complexity of a hashmap assumes everything easily fits in uniform-access memory.
In fact, you could use 512bits primary key with MySQL and still, range queries would be 10x faster and 10x less space in ram than in Postgres. This article explains why that is.
Most clustered tables don’t have a single last page. For ex it’s common to order a table by (used_id,pk) so a users data is grouped together. Dropbox did this
For the ones which do have a single last page, it’s easy to remove that, you don’t have to use sequential IDs. Use a uuid.
Basically this problem only happens when you cluster globally by mistake. just don’t make that mistake.
Why do you believe a database should order rows on disk?
If your rows are not ordered on disk, the amount of data you need to load to query 100 rows is insane
10kb query result (100 rows 100 bytes) requires almost 1mb of data to be loaded- it’s 99% waste
Postgres is 100x slower than other DBs for range queries
Every single other database in existence has this feature except for Postgres
> 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!
If you are worried about size ballooning, rather than the randomness, make sure you actually need more than 32-bit standard integers (well, 31-bit as they tend to be signed and we usually start from 0 or 1 not -2,147,483,648).
Avoiding roll-over issues is sometimes a valid concern sometimes with 32-bit INTs, but I've seen people specify 64-bit surrogate keys when their data is not likely to grow to where 31 would be an issue in the next few hundred years… There is an argument that 64-bit values are more efficient in modern CPUs, but I've not seen any good tests that show a measurable difference in the context of DB keys where there are other overheads to consider due to the doubling in size.
# Transactions that are explicitly rolled back, which have inserted to a table with an IDENTITY (or equivalent) column, almost always result in such a gap. Though if this is happening enough that it pushes the count up by an order of magnitude over time, you probably have a design problem…
# To reduce locking issues on the counter many DBs hold a cache of values (SQL Server allocates 1,000 at a time) in the persisted count so after a shutdown, especially an unclean shutdown, or a fail-over if using one of the clustering/mirroring/options options for HA, it is possible that most of these will be skipped. If this is happening enough to be a long-term problem than you have significant infrastructure issues. Such a cache could be per-thread/-process (IIRC it isn't in SQL Server) which is one of the reasons that IDENTITY column values can seem to be out-of-order in high concurrency environments (though you should never care about the actual order of values in such columns so that is a non-issue).
# In some DR processes where old DBs are restored, the values may be artificially updated after restore if used values might have been exposed to an external service (to avoid confusion caused is a number is used twice from the point of view of that external service). This is an extra argument against exposing internal ID values to external systems and in favour of having an additional UUID based identifier for such purposes.
# Also, though this is the most obvious one and hardly needs stating, deleted rows won't “return” their now unused number to be reused. You should scale the type based on rows expected to be inserted, not rows expected to be kept long-term.
If you are expecting hundreds of millions of rows in the lifetime of the table then a type larger than 32-bit is worth considering despite the extra storage needed in data and index pages. I'd not criticise considering it for tens of millions if you want to be more paranoid. Otherwise: 32-bit is very unlikely to not be fine, and 64-bit overkill.
These recommendations are database-specific. It is definitely true of MySQL, since its row storage hinges on the primary key (and other indices yield that primary key). To have a hot page cache, you need to always add to the same page, so an incremented primary index is preferred. A UUIDv4 secondary index would still have cold page caches though, defeating the purpose. (Unless using UUIDv7.)
But in CockroachDB, the data is distributed. Random INSERTs actually have a speedup over sequential ones, as those insertions can happen in parallel (on different machines). Similarly, SELECTs are faster if the primary index is random, because a single machine is not overloaded; it effectively acts as a load balancer.
It is wrong to think that distributed databases do not need sequences. YugabyteDB allows it. With YugabyteDB you use hash sharding to distribute them to a small number of hash ranges, so that they don0t go all at the same place, but are not scattered across the whole database. CockroachDB and Spanner doesn't have hash sharding and that's why they do not recommend sequences. There are also use cases where range sharding on the sequence is good when you don't need to distribute the data ingest, but benefit from their colocation when querying.
A covering index always has large keys too.
In SQLite3 the trade-off made is that B-trees have either integer keys and arbitrary values, or arbitrary keys and integer values. When using WITHOUT ROWID the whole row is the key. (IIRC)
Why don't let the user set that up on their browser
Ah so that's what the "planet scale" name refers to /j
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)
- direction
- straight ahead
- civics
- propriety
- Rude: "coarse, rough, unfinished, unlearned" (https://www.etymonline.com/word/rude#etymonline_v_16610)
- Mean: "shared by all, common, general" (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.
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.