Bulk-load algorithm for MX-CIF quadtree

My application loads a collection of ~100k items (rectangles) from a map file, then builds a MX-CIF quadtree as an index for fast lookup. The quadtree is built at startup and its contents do not change at runtime.

(In an MX-CIF quadtree, items are stored by the smallest node that fully contains it... both internal and leaf nodes may contain items)

In the first pass, I find the outer extents of the collection, so I know how large the root node is.

In the second pass, I add each item to the smallest node that fully contains it. Once a node passes a certain number of items, it gets spl开发者_StackOverflow社区it and the children are redistributed among the new parent and 4 child nodes.

Given that I have all of the items up-front, how could I build the tree more efficiently?

Do you really need an MX-CIF tree? For rectangles I would propose using either an X-Tree or an PH-Tree.

X-trees are derived from R-trees and have excellent insertion times if you know the whole dataset in advance (bulk loading). They also have very good range query performance. An example implementation can be found here: XXL Library

The PH-Tree is slightly slower on bulk loading, but much faster if objects are updated/moved afterwards. Range query performance is similar to the X-tree, but the PH-tree is faster when extracting small result sets (main cost lies in extracting values, while for the X-tree the main cost lies in processing the query (finding the first node, ...)). An PH-tree implementation is available here: PH-Tree

Disclaimer: I was involved in developing the PH-tree.