On Jan 21, 2016, at 5:14 AM, Simon Riggs wrote:
Sorry, didn't get it.
Certainly for B-Tree we can organize insert buffer (or pending list) as sorted array or also as a tree.
But in both case complexity of search in this buffer will be O(log(N)), not O(1).
O(1) is possible only if we will use hash table for pending list and are lucky with hash function.
But in this case it will be not possible to support range queries and proper order.
In any case, necessity to perform two searches instead of one and combining results will significantly complicate index implementation.
But definitely this solution is more convenient and transparent for users...