How many pages has the index
A database builds an index, a B+ tree in which all keys lie in the leaves and the pages above only direct the search. Keys arrive one at a time and go into the leaf that the descent from the root leads them to: the last leaf in order whose first key is not greater than the new one (or the very first leaf, if the new key is smaller than all). A leaf holds at most C keys. When the (C + 1)-th key arrives in a leaf, the leaf splits.
half, in half: the first ⌊(C + 1)/2⌋ keys stay in the old leaf, the rest go to a new leaf immediately to its right.edge, the same but with one exception, as in SQLite: if the new key is larger than all keys of the index, the old leaf stays full, and the new key alone opens a new leaf on the right.
How many leaves will the index have when all keys are inserted? The second and third tests are an index of the words of “War and Peace”: keys arrive in text order, and the key is the rank of the pair “word, position in the text” in alphabetical order. The fourth and fifth are an index of the times of earthquakes from the USGS catalogue: keys arrive in increasing order.
Input
The first line holds n, C and the split rule (1 ≤ n ≤ 2·10⁵, 2 ≤ C ≤ 1000, the rule is half or edge). The second holds n distinct integer keys from 0 to 10⁹ in insertion order.
Output
The number of leaves.
Examples
Example 1
10 4 half 1 2 3 4 5 6 7 8 9 10
4
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The pages above the leaves only choose which leaf to go down to. Does this choice depend on how the upper storeys are built? What is it enough to know about the leaves to find the right one?
2Hint 2
Keys are never deleted, so after a split the first key of a leaf never drops below the separator assigned to it. The leaf can be found by binary search over the first keys of the leaves.
3The idea
Keep the leaves in a list in order, and next to it a list of their first keys. A new key finds its leaf by binary search over the first keys and takes its place in the leaf, and on overflow the leaf splits and the new leaf is inserted into both lists right after the old one. This is a two-storey B-tree: the list of first keys plays the role of all the upper pages at once.
4Walkthrough
Why the upper storeys do not matter. The separator that goes up into the parent at a split is the first key of the new right leaf, and the descent sends into that leaf exactly the keys not less than the separator. Keys are only added, so the first key of the right leaf stays equal to the separator, and the first key of the leftmost leaf to the smallest key. So “the leaf the descent leads to” is the last leaf whose first key is not greater than the new one, however the internal pages split.
The edge rule checks the new key against the largest in the whole index, not in the leaf: such a key always arrives in the last leaf. Inserting into the middle of the lists shifts the tail, but there are C/2 times fewer leaves than keys, and the shift is a fast memory copy.
The numbers of the tests say the same as the article. On the words of the novel in text order with C = 128 the leaves are 61 % full, worse than the theoretical 69 % for random order: the positions of each word come in increasing order. On the times of earthquakes with half the leaves are exactly half full, with edge almost completely, and there are half as many leaves.
4+Solution
5Complexity
O(n log n) for finding leaves and O(C) for inserting into a leaf; inserting into the lists of leaves is an O(n/C) shift, rare and fast. Memory O(n).
6Common mistakes
edgeby the largest in the leaf. Then a full leaf in the middle of the index does not split in half but cuts off a new one-key leaf, and everything goes differently from there: on the third, seventh and tenth tests the number of leaves does not match.- The wrong leaf for the smallest key. A key smaller than all goes into the very first leaf, and that leaf's first key changes.
- Finding the leaf by a scan. In the sixth test there are more than seventeen thousand leaves, and a scan for every key is hundreds of millions of steps per test.