You seems to know what you’re talking about, have you heard of Juliana trees? Like trees based only on the keys, so searching for a key takes len(key) time.
Bet there is an other name for it but I so remember like that and no web search says anything about it so I’m trying my luck here :-)