It looks to me like most of the work in a view query happens in View::updateQueries. In particular, it uses std::lower_bound and std::upper_bound to find the desired ranges by searching over a timestamp index. My C++ reference states that these are binary searches, with O(log N) complexity. If you look in Bag::doWrite, you can see this index being updated as new data is written to the bag file.