A Question

[Misaka19327]

I am implementing the art tree step by step according to the code of this project. In the process, I have a question that I haven't figured out yet and I would like to ask. That is, the processing of the node16 node in the index function.

According to my understanding, the storage logic of key and children of node4 and node16 is the same, that is, the index of a byte in key is the position of its child node in children. That being the case, I don't understand what the introduction of bitmaps and masks in node16 actually does?

These setences above is translated by Google.

func (a *artNode[T]) index (c byte) int {
	switch a.kind {
	case Node4:
		node := a.node4()
		for index := 0; index < int(node.childrenNum); index++ {
			if node.keys[index] == c {
				return index
			}
		}
	case Node16:
		node := a.node16()
		bitfield := uint(0)
		for index := uint(0); index < node16Max; index++ {
			if node.keys[index] == c {
				bitfield |= 1 << index
			}
		}
		mask := (1 << node.childrenNum) - 1
		bitfield &= uint(mask)
		if bitfield != 0 {
			return bits.TrailingZeros(bitfield)
		}
        ...
}

[plar]

This was an attempt to save memory, but it wasn't worth it. See the updated version. I recently refactored the code significantly.