Seriously. S2 is just quadtrees over a cubemap, with a nice mapping from integers to cells.

So, instead of using a quadtree (because it's "complicated"), they chose to make their own two-level tree requiring O(N) linear scans at both levels, as opposed to O(1) with a simple trick.