Question

I'm trying to implement B+ trees using c. Can you suggest a way to read sorted data from file and store in a B+ tree in O(n) time. Normally it is accomplished in O(nlog(n)) time, is there a way to do it in linear time???

Answer 1

I think that you can't really take advantage of the data being sorted, right? The only time that you can take advantage of it is at the de facto insertion step, but this cost will be dominated by the search for the correct leaf to input and O(n) of going through each and every chunk of data.
In other words, I think that you can't reach O(N) because only dealing with the auxiliary data (reading every element from file) involves a cost of already O(N). The only way that it may work is to have a variable keeping track of where to input the next element, but still, I think you can't reach O(N). I may be wrong though. If anything, you have to reduce search operation on the tree to a minimum(and root splitting also, I think), so you can consider it O(1) as N gets larger.

Answer 2

Well is it possible to achieve constant time or O(1) time for each leaf or O(n) time for n leaves, by using pre-order traversal or in-order traversal or storing the leaves in the file.?