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

61–70 of 84 posts

Re: B-Trees and Database Indexes

#61

Post by [deleted] »

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.

[deleted]

Re: B-Trees and Database Indexes

#62

Post by bddicken »

seanman wrote: post #58

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…

Thanks Sean! Yeah that would be very cool to have an interactive visual for that as well. So many possibilities!

Re: B-Trees and Database Indexes

#63

Post by bddicken »

yosri-xp wrote: post #18

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. 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…

You're welcome! Sharding with B tree indexes... Hmmm, I know a company that does that.

Re: B-Trees and Database Indexes

#65

Post by infogulch »

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.

Oxide Computer published their Request for Discussion (RFD) site software [1] that they use for internal published documentation and discussion. Many are published to the public, but some are private. [2] They talk about how they use it and where it came from in their most recent podcast: RFDs: The Backbone of Oxide [3].

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

Re: B-Trees and Database Indexes

#66

Post by sgarland »

paxys wrote: post #53
hobs wrote: post #51

Earlier quoted context omitted.

Basic incremental counters work for most real world production constraints. Most people are not going to create tables with 4.2 billion rows, even with failed inserts. If you are doing that its an extreme of either very much you know what you are doing, or you very much do not; I have seen both in production.

What if I have multiple partitions? Replication? What if I don't want business data to be exposed due to strictly incremental counters? What if I want unique IDs across different tables?

Partitions should not impact the use of an INT PK, except that you’ll need to include the partition key in the PK, e.g. (id, created_at) if partitioning by datetime. The displayed ordering without an explicit ORDER BY may not make sense, but to be fair, there are never any guarantees about implicit order.

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.

Re: B-Trees and Database Indexes

#67

Post by weaksauce »

fabian2k wrote: post #40
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…

There are cases where it is really useful to have only universally unique IDs, e.g. if you have multi-tenant systems and at some point you need to move tenants to a different server/instance or merge tenants on the same DB.

they do mention that it’s is good to have both. also using a newer uuid version that is more sortable temporally is also wise.

> 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!

Re: B-Trees and Database Indexes

#68

Post by paperplatter »

espadrine wrote: post #55
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…

> Use regular bigserial (64bit) PKs for internal table relations and UUIDs (128bit) for application-level identifiers and natural keys 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 U…

Yeah, Spanner is also clear about this. It doesn't even have sequences, and their docs say to use random pkeys rather than time-dependent things like uuid7.

Re: B-Trees and Database Indexes

#69

Post by paperplatter »

dspillett wrote: post #43
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…

> Use regular bigserial (64bit) PKs for internal table relations and UUIDs (128bit) for application-level identifiers and natural keys. 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 so…

It's not just about the data size. There are reasons your sequence can increment without a row actually being inserted.

Re: B-Trees and Database Indexes

#70

Post by paperplatter »

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?

Yes, if a client gives a UUID and you want to look up relations to that table, you'll have to join with that table. And the index on the UUID has its own costs. It's still better this way. If for some rare reason this join is too expensive, there are other options like using a cache or denormalizing the tables slightly. The alternative of a UUID pkey will seriously slow down every join.

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.

Post reply on HN