0

I am creating a unique ID generator for my application. I am reading everywhere that monotonic keys make life easier for the b-tree. I generate an ID by combining a time part and a random part, the result is a BIGINT. 30 inserts over a month time would look like:

161382496505555475
161383496513869363
161384566521269728
161387696534951408
161391066542917771
161395676557845188
161396876568927786
161403566572243244
161406876581461654
161411576592302253
161432366601557433
161454566612380546
161497816626330847
161498126638855404
161522016645286994
161542136651268281
161552156668048334
161556516672713275
161567476682846578
161587696692945392
161598426706622187
161599986719703849
161602466723494896
161633486735133538
161634866748327052
161654886754576805
161665966765069819
161686876779287376
161688676786669774
161699126792749601

The first 11 digits are always sequential, the last 7 digits are always random. Would this work well on a PostgreSQL 12 index?

4
  • With 30 inserts per month, you don't need to worry about performance in the next 10000 years or so. – a_horse_with_no_name Feb 20 at 14:53
  • This set of 30 is only an example to demonstrate how the time part evolves over a time period of a month (1613824965 - 1616991267), in real life the number of inserts will be higher. It won't last 10,000 though, as this timestamp runs out of the BIGINT range (9223372036) after about 241 years from now ;-) – svenema Feb 20 at 21:03
  • Well a proper timestamp could store values until the year 294276 ;) – a_horse_with_no_name Feb 20 at 21:05
  • This ID is generated to function as a GUID of sorts, hence the random part. The random part allows for sub-second key generation from multiple source (some of which may be offline). 241yrs is a good trade off in this case. – svenema Feb 20 at 21:09
1

With B-Tree indexes, more importantly is the cardinality of the data you're indexing. The more unique the data is in the index, generally the better candidate it is for a B-Tree index because it'll result in a much more full tree with many branches and leaves. A very non-unique field, like a boolean based field, will always only have two distinct values, and therefore is very repetitive resulting in two short but wide branches and doesn't filter down the data as much as a more unique field.

Since you're planning to index a BIGINT field with randomized values, it should lead to very unique data and the B-Tree index should perform very well, regardless of the monotonicness of those values. Additionally, if you're only inserting 30 values a month, your table must be tiny so you should have no worries at all regarding using a B-Tree index. B-Tree indexes handle billions of rows just fine.

To answer your actual question, yes monotonic values in a B-Tree index reduce fragmentation initially and therefor are more efficient, but again this is probably a minimal concern based on the fact that your values will be very unique and your overall amount of data being tiny.

2
  • wouldn't reversing the time and random parts (random part first) result in an wider (=better) b-tree? – svenema Feb 20 at 21:25
  • @svenema No because each node in the tree is the full value of each data point that's indexed, and B-Trees are generally always balanced (one of the words that the B in B-Tree stands for). In other words, the values 123, 124, and 137` are equally as random and equal in cardinality as 321, 421, and 731. – J.D. Feb 21 at 3:59
1

Yes, if you have values that increase monotonically, the B-tree index will end up densely packed. Subsequent updates and deletes will still lead to fragmentation, but that is normal.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.