skip to content

How does a wider branching factor change what one structurally shared update has to copy?

level: middleimportance: should knowfreq 40%

answer

  1. one knob, two directions
  2. depth is the log, base b
  3. fewer nodes, fatter nodes
  4. references copied scale with the width
  5. depth collapses to a small constant

basics

~10 s

Wider nodes make the tree shallower, so fewer nodes are rebuilt per update — but each rebuilt node now carries more child references to copy. Fewer allocations, more references copied inside each.

solid answer

~40 s

The route's length is the tree's depth, which for `n` elements and a branching factor of `b` is about log-base-b of `n`. Widening `b` shortens that route, so an update allocates fewer nodes and a read follows fewer hops. What you pay is per node: each rebuilt node copies `b` child references instead of a handful, so the references copied per update run at roughly `b` times the depth, and that product grows as `b` grows. Wide nodes still tend to win, because copying a short contiguous run of references is cheap next to allocating and chasing one extra node per level, and because at realistic sizes a wide branching factor collapses the depth to a small constant.

go deeper

for a junior

Hold on to the direction: more children per node means a shallower tree, and a shallower tree means fewer nodes to rebuild when one element changes.

for a middle

Quote both terms and their directions — nodes rebuilt fall with the log of the width, references copied rise with the width — and say which one dominates in practice and why.

for a senior

Reason about the sparse case and about memory per version, and be ready to say what measurement would tell you the chosen width is wrong for a real workload.

for a principal

Treat the width as a design parameter set against read/write mix, element count and memory budget, and say what evidence would justify changing it.

Branching factor is the one tuning knob this mechanism has, and it trades **number of nodes rebuilt** against **references copied inside each node**. ## The two quantities For a tree holding `n` elements with `b` children per node: - **Depth** is about log-base-b of `n`. That is the number of nodes a single-position update rebuilds, and the number of hops a read follows to reach an element. - **References copied per update** is about `b` times that depth, because each rebuilt node copies its whole slot array with one entry swapped. Those move in opposite directions. Raising `b` divides the depth by the log of `b` but multiplies the per-node copy by `b`. ## Putting numbers on it Take the hourly snapshot of a directory tree holding roughly a million entries: | Branching factor | Levels rebuilt per update | References copied per update | |---|---|---| | 2 | about 20 | about 40 | | 4 | about 10 | about 40 | | 32 | about 4 | about 128 | | 1024 | 2 | about 2048 | Read the table honestly: the reference count is actually **smallest at a very small branching factor** and grows as `b` grows, while the node count falls fast at first and then barely moves. So the wide node is not winning on raw reference count. It wins on the things the table does not show: 1. **Allocation and indirection dominate.** Each level costs an allocation and a pointer hop. Twenty of those is far worse than four, even when four of them copy more slots between them. 2. **A contiguous run of references copies cheaply.** Copying several dozen adjacent references is a single bulk move; visiting sixteen extra nodes is sixteen scattered memory accesses. 3. **Depth collapses to a constant in practice.** Past a certain width, the depth for any size a program will really hold is a small fixed number of levels, so lookups and updates behave like fixed-cost operations rather than logarithmic ones — which is how these structures get described as "effectively constant time". ## What widening costs - **More memory per version.** Each rebuilt node is wider, so the route costs more bytes even though it holds fewer nodes. - **Waste in sparse nodes.** A wide node that holds three live children still carries its full slot array; structures that expect sparsity usually record which slots are occupied and store only those, which is the idea behind a **hash array mapped trie**. - **Coarser sharing at the edges.** Two versions share whole subtrees, and a subtree is a node's worth of children. A wider node is a bigger unit of rebuild: every update reissues `b` references even to change one. ## What does not change Branching factor changes the constants and the depth. It does not change the shape of the mechanism at all: - The update still rebuilds exactly one route and shares everything off it. - No existing node is written, at any width. - The cost still scales with the **depth** of the structure rather than with the number of elements — which is the property that makes immutable updates affordable in the first place. ## How to answer this in an interview Say the trade in one line — *wider nodes mean fewer, fatter rebuilds* — then give the direction of each term: node count down with the log of `b`, references copied up roughly linearly in `b`. Then say why implementations pick wide anyway: at a realistic element count the depth becomes a handful of levels, and bulk-copying a slot array is cheaper than the allocations and pointer chases that the extra levels would have cost. That answer shows you know the arithmetic *and* that you know why the arithmetic is not the whole story.

  • Does a wider branching factor reduce the total number of references copied per update?
    No — it increases it. The references copied run at about the width times the depth, and that product grows once the width is large. What falls is the number of nodes allocated and the number of pointer hops, which is usually what dominates.
  • Why is a very wide node wasteful when most of its slots are empty?
    Because the rebuilt node still carries its full slot array, so a sparse tree pays width per level in both memory and copying. Implementations answer this by recording which slots are occupied and storing only those.
  • What stays the same no matter the branching factor?
    The mechanism: one root-to-leaf route is rebuilt, everything off it is reused by reference, and no existing node is ever written. Width changes the depth and the constants, not the rule.

saying these in an interview costs you the question

  • Says a wider node makes everything cheaper with no cost
  • Thinks depth is proportional to the element count, not its logarithm
  • Believes a wide branching factor lets the update skip rebuilding the root
  • Confuses copying a node's references with copying its subtrees
  • Calls the update constant time without saying the depth is a small constant in practice