  We study learning-augmented binary search trees (BSTs) and B-Trees via Treaps
with composite priorities. The result is a simple search tree where the depth
of each item is determined by its predicted weight $w_x$. To achieve the
result, each item $x$ has its composite priority
$-\lfloor\log\log(1/w_x)\rfloor + U(0, 1)$ where $U(0, 1)$ is the uniform
random variable. This generalizes the recent learning-augmented BSTs
[Lin-Luo-Woodruff ICML`22], which only work for Zipfian distributions, to
arbitrary inputs and predictions. It also gives the first B-Tree data structure
that can provably take advantage of localities in the access sequence via
online self-reorganization. The data structure is robust to prediction errors
and handles insertions, deletions, as well as prediction updates.
