search

datacrypt-project / hitchhiker-tree

Functional, persistent, off-heap, high performance data structure
Eclipse Public License 1.0
1.19k stars 64 forks source link

Doc issue: No rebalance ? #20

Closed xcombelle closed 7 years ago

xcombelle commented 7 years ago

Looks like in your doc you speak never about rebalancing the tree Does it means that it is never rebalanced ? If it is the case doesn't mean that in the case of insertion in sorted order, access to your tree is linear ?

dgrnbrg commented 7 years ago

Every time an operation would be flushed to a leaf, that operation goes through the standard B+ tree algorithm, which will rebalance the tree. Even in sorted order insertion, we still end up with a balanced tree!