We present a numerical method for solving the scalar advection-diffusion equation using adaptive mesh re- finement. Our solver has three unique characteristics: (1) it supports arbitrary-order accuracy in space; (2) it allows different discretizations for the velocity and scalar advected quantity; and (3) it combines the method of characteristics with an integral equation formulation. In particular, our solver is based on a second-order accurate, unconditionally stable, semi-Lagrangian scheme combined with a spatially-adaptive Chebyshev octree for discretization. We study the convergence, single-node perfor- mance, strong scaling, and weak scaling of our scheme for several challenging flows that cannot be resolved efficiently without using high-order accurate discretizations. For example, we consider problems for which switching from 4th order to 14th order approximation results in two orders of magnitude speedups for a fixed accuracy. For our largest run, we solve a problem with one billion unknowns on a tree with maximum depth equal to 10 and 14th-order elements on 16,384 cores on the ”STAMPEDE” system at the Texas Advanced Computing Center.