One of idea is add sorting of Datums to be splitted by cost of insertion. It's implemented in intarray/tsearch GiST indexes.
Yes, it's a good compromise between linear and quadratic entries distribution algorithms. In quadratic algorithm each time entry with maximal difference of inserion cost is inserted. Quadratic algorithm runs slowly than sorting one, but on my tests it shows slightly better results.
Can we figure out some information about index i.e. whet is the height of index tree, how many values are placed in one leaf node and one non leaf level node?
