AFAICT the query is about "the next unbooked interval of at least a given duration". I assume the problem with the B-tree is that when the schedule is contentious, it essentially degenerates into a scan for the next large gap. (And when it's not contentious, the B-tree will be approximately optimal so there'd be no point looking for a better data structure for that regime).
To improve queries that are contentious I'd try build something like a R-tree or range/interval-tree of the unbooked intervals (the complement of the booked intervals). One invariant will be that availability intervals are placed at the highest possible layer in the tree (the smallest region that they entirely fit inside). Then query the R-tree (or interval tree) but only to the depth corresponding to the interval size requested. (Any lower levels would contain only availability windows that are too small, so we can skip searching them).
That would avoid scanning all the small intervals. Not sure how much overhead this would add and if it would work out significantly faster than your B-tree though...
Comments
AFAICT the query is about "the next unbooked interval of at least a given duration". I assume the problem with the B-tree is that when the schedule is contentious, it essentially degenerates into a scan for the next large gap. (And when it's not contentious, the B-tree will be approximately optimal so there'd be no point looking for a better data structure for that regime).
To improve queries that are contentious I'd try build something like a R-tree or range/interval-tree of the unbooked intervals (the complement of the booked intervals). One invariant will be that availability intervals are placed at the highest possible layer in the tree (the smallest region that they entirely fit inside). Then query the R-tree (or interval tree) but only to the depth corresponding to the interval size requested. (Any lower levels would contain only availability windows that are too small, so we can skip searching them).
That would avoid scanning all the small intervals. Not sure how much overhead this would add and if it would work out significantly faster than your B-tree though...