ART 自适应基数树内部剖析：Node4/16/48/256 节点分裂、乐观路径压缩与内存数据库索引的缓存级优化

TERM = 0x00   # key 末尾终止字节：保证没有任何 key 是另一个 key 的前缀

def enc(key):
    return bytes(key) + bytes([TERM])

class Leaf:
    __slots__ = ("key", "value")
    def __init__(self, key, value):
        self.key = key            # 存完整 key：乐观压缩的正确性兜底
        self.value = value

class Node:
    __slots__ = ("prefix", "keys", "children", "cap")
    CAPS = (4, 16, 48, 256)      # 四档自适应容量
    def __init__(self, prefix=b"", cap=4):
        self.prefix = bytes(prefix)   # 被压缩掉的公共前缀（乐观：查找时只跳过）
        self.keys = []                # 子节点首字节，保持升序
        self.children = []
        self.cap = cap

    def find(self, b):
        # Node4/16 线性扫描；真实实现 Node16 用 SSE2 一次比 16 字节
        for i, k in enumerate(self.keys):
            if k == b:
                return i
        return -1

    def add(self, b, child):
        pos = 0
        while pos < len(self.keys) and self.keys[pos] < b:
            pos += 1
        self.keys.insert(pos, b)
        self.children.insert(pos, child)
        return len(self.keys) > self.cap   # 是否溢出、需要升级

class MiniART:
    def __init__(self):
        self.root = None
        self.size = 0
        self.nodes = {4: 0, 16: 0, 48: 0, 256: 0}
        self.upgrades = 0

    def _upgrade(self, n):
        i = Node.CAPS.index(n.cap)
        if i + 1 >= len(Node.CAPS):
            return n                       # 已是 Node256
        bigger = Node(n.prefix, Node.CAPS[i + 1])
        bigger.keys = n.keys[:]
        bigger.children = n.children[:]
        self.nodes[n.cap] -= 1
        self.nodes[bigger.cap] += 1
        self.upgrades += 1
        return bigger

    def get(self, key):
        k = enc(key)
        node = self.root
        depth = 0
        while isinstance(node, Node):
            p = node.prefix
            if k[depth:depth + len(p)] != p:
                raise KeyError(key)        # 乐观压缩下也可提前排除
            depth += len(p)
            idx = node.find(k[depth])      # 终止字节保证下标一定存在
            if idx < 0:
                raise KeyError(key)
            node = node.children[idx]
            depth += 1
        if node.key != k:                  # 末尾完整 key 校验，防假阳性
            raise KeyError(key)
        return node.value

    def put(self, key, value):
        k = enc(key)
        if self.root is None:
            self.root = Leaf(k, value)
            self.size += 1
            return
        self.root = self._insert(self.root, k, value, 0)

    def _insert(self, node, k, value, depth):
        if isinstance(node, Leaf):
            old = node.key
            if old == k:
                node.value = value
                return node
            d = depth
            while old[d] == k[d]:          # 终止字节保证必在某处分叉
                d += 1
            n = Node(k[depth:d], 4)        # 新建公共前缀节点
            self.nodes[4] += 1
            n.add(old[d], Leaf(old, node.value))
            n.add(k[d], Leaf(k, value))
            self.size += 1
            return n

        # 内部节点：先检查压缩前缀是否仍匹配
        p = node.prefix
        i = 0
        while i < len(p) and p[i] == k[depth + i]:
            i += 1
        if i < len(p):
            # 前缀在第 i 字节分叉：造新父节点，原节点下移一层
            split = Node(p[:i], 4)
            self.nodes[4] += 1
            node.prefix = p[i + 1:]
            split.add(p[i], node)
            split.add(k[depth + i], Leaf(k, value))
            self.size += 1
            return split

        depth += len(p)
        b = k[depth]
        idx = node.find(b)
        if idx < 0:
            overflow = node.add(b, Leaf(k, value))
            self.size += 1
            return self._upgrade(node) if overflow else node
        node.children[idx] = self._insert(node.children[idx], k, value, depth + 1)
        return node

if __name__ == "__main__":
    t = MiniART()
    for i in range(10000):
        t.put(("user:%06d" % i).encode(), i)
    assert t.get(b"user:000042") == 42
    print("size =", t.size, "upgrades =", t.upgrades, "nodes =", t.nodes)

# 承接上一代码块（放在同一文件中，沿用其 t 实例）
NODE_BYTES = {4: 56, 16: 168, 48: 640, 256: 2048}   # 量级估算，含头部与对齐

def stats(t):
    total = sum(t.nodes.values())
    mem = sum(t.nodes[cap] * NODE_BYTES[cap] for cap in t.nodes)
    flat = total * NODE_BYTES[256]                   # 若全部用固定 256 路节点
    return {
        "keys": t.size,
        "nodes": t.nodes,
        "upgrades": t.upgrades,
        "node_bytes": mem,
        "bytes_per_key": round(mem / max(t.size, 1), 1),
        "vs_fixed_256x": round(flat / max(mem, 1), 1),
    }

def walk(node, out):
    if hasattr(node, "key"):
        # 乐观压缩不存完整路径，叶子里的完整 key 才是唯一可信来源
        out.append((node.key, node.value))
        return
    # children 与升序 keys 一一对应，DFS 顺序即字典序
    for ch in node.children:
        walk(ch, out)

def iter_prefix(t, prefix):
    out = []
    if t.root is not None:
        walk(t.root, out)
    p = bytes(prefix)
    # 叶子 key 末尾带终止字节，输出时去掉
    return [(k[:-1], v) for k, v in out if k.startswith(p)]

print(stats(t))
print(iter_prefix(t, b"user:00000")[:3])