Topic: Check whether internal nodes also carry sibling pointers (they shouldn't need to in a single-threaded implementation, confirming the L&Y distinction)

Date: 2026-05-29

Time: 10:52

Internal Nodes Do Not Carry Sibling Pointers — Confirming the L&Y Distinction

The answer is definitive: internal nodes have no sibling pointer; only leaf nodes do. This is visible directly in the serialization formats.

Leaf layout (from serializeleaf, btree.py:~176)


[type:1B][num_keys:2B][next_sibling:4B] ([key_len:2B][key][val_len:2B][val])...

The next_sibling field is a 4-byte page number written immediately after the 3-byte header (line ~178 in the observation):


buf += struct.pack('>I', next_sibling)

The sentinel NO_SIBLING = 0xFFFFFFFF (line 13) marks the rightmost leaf.

Internal layout (from serializeinternal)


[type:1B][num_keys:2B][child₀:4B] ([key_len:2B][key][child:4B])...

The 4 bytes after the header are child₀ — the leftmost child pointer — not a sibling link. There is no sibling field anywhere in the internal node format. The entry on serializeinternal confirms it takes only (keys, children) as parameters, with no sibling argument. Similarly, deserializeinternal returns only (keys, children) — a 2-tuple, versus the 3-tuple (keys, values, nextsibling) from deserialize_leaf.

Why this confirms the Lehman & Yao distinction

In Lehman and Yao's B-link tree (1981), every node — internal and leaf — carries a right-link (sibling pointer) plus a high key. This is essential for correctness under concurrent access: when a reader descends to a node that has been split by a concurrent writer, the right-link lets the reader move sideways to the correct half without re-traversing from the root.

This implementation is single-threaded. No concurrent reader can observe a half-finished split, so internal nodes don't need sideways navigation. Leaf nodes retain sibling pointers for a different reason entirely: they enable efficient rangescan and iteration (iter_) by chasing the leaf chain without re-traversing the tree from the root for each successor.

The structural asymmetry — siblings on leaves but not on internals — is the hallmark of a classic B⁺-tree rather than a B-link tree.

Beliefs