Shuttle tree algorithm complexity:
- Search(optimal):
$O(\log_{B+1}N)$ - Range query of
$L$ successive elements (Optimal):$\log_{B+1}N + L/B$ - Insertion:
$\frac{\log_{B+1}N}{B^{\Theta(\frac{1}{(\log\log B)^2})}+\frac{(\log^2 N)}{B}}$
A shuttle tree is a strongly weight-balanced search tree (SWBST). Each non-leaf node points to a a linked list of buffers. These buffers are recursively defined to be shuttle trees.