  In this paper, we revisit the question of how the dynamic optimality of
search trees should be defined in external memory. A defining characteristic of
external-memory data structures is that there is a stark asymmetry between
queries and inserts/updates/deletes: by making the former slightly
asymptotically slower, one can make the latter significantly asymptotically
faster (even allowing for operations with sub-constant amortized I/Os). This
asymmetry makes it so that rotation-based search trees are not optimal (or even
close to optimal) in insert/update/delete-heavy external-memory workloads. To
study dynamic optimality for such workloads, one must consider a different
class of data structures.
  The natural class of data structures to consider are what we call
buffered-propagation trees. Such trees can adapt dynamically to the locality
properties of an input sequence in order to optimize the interactions between
different inserts/updates/deletes and queries. We also present a new form of
beyond-worst-case analysis that allows for us to formally study a continuum
between static and dynamic optimality. Finally, we give a novel data structure,
called the \jellotree, that is statically optimal and that achieves dynamic
optimality for a large natural class of inputs defined by our beyond-worst-case
analysis.
