A shared plain binary search tree index serves several services, some feeding it monotone keys — what is your call?

## Framing the decision This is not a question about which structure is asymptotically better; it is about **where a guarantee should live** when many teams share one component. Three options are on the table, and each is right somewhere. **Option A — fix the callers.** Tell the teams with monotone keys to shuffle their batches, or to bulk-build from their sorted data. Cheapest possible change, no migration, no new dependency. **Option B — fix the structure.** Replace the plain tree behind the existing interface with a height-balanced one (AVL or red-black), so the height bound holds for every caller and every input order without anyone thinking about it. **Option C — accept it.** Document the behaviour and move on, because the sizes involved make a chain harmless. ## Why Option A is weaker than it looks A caller-side fix is a **convention**, and conventions decay. It has three specific weaknesses in a shared component: - **It must be re-learned by every future caller.** The team that onboards next year reads the interface, not the incident review. The interface promises an ordered index; nothing in it says "and please randomise your insertion order." - **The failure is silent.** A caller who forgets gets correct results, passing tests, and a latency cliff that only appears at production scale. There is no signal at the moment the mistake is made, which is the worst property a convention can have. - **You may not own the inputs at all.** If keys derive from untrusted or external data, order is not a matter of discipline — it can be chosen against you, at which point a probabilistic argument is worth nothing. A convention that must hold across teams and across time, with no enforcement and no immediate feedback, is not a fix. It is a scheduled incident. ## Why Option B is usually the call Moving the guarantee into the structure makes the bad case impossible rather than merely discouraged. The cost is concrete and boring: a small amount of extra per-node state, and extra work on every insert and delete to maintain the height invariant. AVL keeps a tighter height bound and does more work per write; red-black accepts a looser bound and does less — a choice worth making on the read/write mix, and a detail well below the level of this decision. What makes it a *principal* call is the rollout, not the data structure: - **Keep the interface.** If the public surface is an ordered index with the same operations, this is an implementation swap, not an API migration. That is what keeps the change from becoming a multi-quarter coordination project. - **Ship observability with it.** Emit height and node count from the start. Height over log2(size) tells you whether the old shape problem was real and confirms the new one is fixed. Without it, you are asking people to trust a claim. - **Do not pause writes.** If the index is live, build the replacement alongside the existing one, verify equality of query results, then cut over. Sortedness helps: a snapshot of the existing keys can be bulk-built into a balanced tree in O(n) by recursive median selection. - **Buy, do not hand-roll.** A balanced tree written in-house is a piece of subtle code your team owns forever, and its bugs are correctness bugs, not performance ones. Use a well-tested implementation unless there is a strong reason not to. ## When Option C is genuinely correct Asymptotics are about growth, and growth only matters if the input grows. If the index holds a few hundred configuration entries, is rebuilt at startup, and is never on a request path, a chain of a few hundred nodes costs microseconds and the migration buys nothing. The honest senior move is to say so, with the two conditions written down: **bounded size** and **off the hot path**. Add an assertion or a metric that fires if the size assumption is ever violated, because the thing that turns Option C from pragmatic to negligent is the index quietly becoming large. ## Deciding, out loud The reasoning I would want to hear from a candidate: identify who controls the ordering; note that in a shared component the answer is "nobody, permanently"; observe that the failure mode is silent and cumulative rather than loud and self-correcting; conclude that the guarantee belongs in the structure; then bound the claim by naming the case where it does not — small, fixed, cold data — and by pricing what the guarantee costs on the write path. A candidate who reaches for the balanced tree with no cost discussion is reciting; a candidate who defends the convention because the migration is expensive has misjudged which risk compounds. ## The one-line version Prefer the structure that makes the bad case impossible over the discipline that must be re-enforced by every caller — and say explicitly what that guarantee costs per write and where it is not worth paying.