I wouldn’t have picked 65,536, too, but there’s a trade-off between the increment and the number of items you can append without running into problems.
If he had picked 2^63, it wouldn’t be possible to create an initial list of even 2 items.
Depending on the use case, I probably would have picked 2^54 or so (allows for appending about a thousand items)
If your lists are small it doesn’t matter much what you do, but for large lists, I don’t think there’s a clean solution for this, if one keeps the key size constant.
If you have a known large number N of items to insert up front, and future inserts will be random, you can do the reindexing to 2^64 / N in advance. (Perhaps there's a further optimization in rounding N up to the next power of 2).
N = 2^48 is what gives you his strategy of numbering the initial entries in increments of 65536.
Comments
I wouldn’t have picked 65,536, too, but there’s a trade-off between the increment and the number of items you can append without running into problems.
If he had picked 2^63, it wouldn’t be possible to create an initial list of even 2 items.
Depending on the use case, I probably would have picked 2^54 or so (allows for appending about a thousand items)
If your lists are small it doesn’t matter much what you do, but for large lists, I don’t think there’s a clean solution for this, if one keeps the key size constant.
If you have a known large number N of items to insert up front, and future inserts will be random, you can do the reindexing to 2^64 / N in advance. (Perhaps there's a further optimization in rounding N up to the next power of 2).
N = 2^48 is what gives you his strategy of numbering the initial entries in increments of 65536.
2^64/(N+1), you mean ;-)
But yes, the more you know, the better your invitation guess can be. That’s why I wrote “depending on the use case”.