A node256 is nearly 4KB in memory whereas a node48 is closer to 1KB, so there is a potential for anywhere up to 75% memory savings in some subject spaces.
Implemented as per the ART paper, although with the caveat that our pointers are actually 16 bytes (as interface{}s) rather than 8 bytes as the paper assumes:
Node48: As the number of entries in a node increases, searching the key array becomes expensive. Therefore, nodes with more than 16 pointers do not store the keys explicitly. Instead, a 256-element array is used, which can be indexed with key bytes directly. If a node has between 17 and 48 child pointers, this array stores indexes into a second array which contains up to 48 pointers. This indirection saves space in comparison to 256 pointers of 8 bytes, because the indexes only require 6 bits (we use 1 byte for simplicity).
A
node256is nearly 4KB in memory whereas anode48is closer to 1KB, so there is a potential for anywhere up to 75% memory savings in some subject spaces.Implemented as per the ART paper, although with the caveat that our pointers are actually 16 bytes (as
interface{}s) rather than 8 bytes as the paper assumes:Signed-off-by: Neil Twigg neil@nats.io