On Mon, Nov 21, 2022 at 3:43 PM Masahiko Sawada <sawada.m...@gmail.com> wrote: > > On Mon, Nov 21, 2022 at 4:20 PM John Naylor > <john.nay...@enterprisedb.com> wrote:
> > Assuming the smallest node is fixed size (i.e. fanout/capacity member not part of the common set, so only part of variable-sized nodes), 3 has a nice property: no wasted padding space: > > > > node4: 5 + 4+(7) + 4*8 = 48 bytes > > node3: 5 + 3 + 3*8 = 32 > > IIUC if we store the fanout member only in variable-sized nodes, > rt_node has only count, shift, and chunk, so 4 bytes in total. If so, > the size of node3 (ie. fixed-sized node) is (4 + 3 + (1) + 3*8)? The > size doesn't change but there is 1 byte padding space. I forgot to mention I'm assuming no pointer-tagging for this exercise. You've demonstrated it can be done in a small amount of code, and I hope we can demonstrate a speedup in search. Just in case there is some issue with portability, valgrind, or some other obstacle, I'm being pessimistic in my calculations. > Also, even if we have the node3 a variable-sized node, size class 1 > for node3 could be a good choice since it also doesn't need padding > space and could be a good alternative to path compression. > > node3 : 5 + 3 + 3*8 = 32 bytes > size class 1 : 5 + 3 + 1*8 = 16 bytes Precisely! I have that scenario in my notes as well -- it's quite compelling. -- John Naylor EDB: http://www.enterprisedb.com