B+HTree, now powering IntelliJ IDEA 11 indices

[nicity]

Last summer I implemented mine own flavor of B+Tree aka B+HTree, H for Hash. Usually O characteristics for B trees are calculated on height of the tree, however insertion of the data to leaf block can be costly. E.g. if key / value pairs are stored as array, one needs to shift at least half of the pairs at insertion. To avoid the problem, the data

Comments

[elizarov]

Can you, please, elaborate what exactly makes it more compact vs hash only. Naively thinking, hash-only solution should occupy as much space as all your leaf nodes.

[nicity]

In short:B+HTree is more compact comparing with our previous hash based solution

[elizarov]

Thank you for description of your original hash based solution. It explains a lot.

Btw, how do you avoid costly mapping/unmapping with B+HTree?

[nicity]

Due to index compactness one needs 2 times less byte buffer segments and this means one can open e.g. IntelliJ Idea code base (20000 files) without remapping byte buffers at all. Once number of keys in index becomes very large (e.g. when encountering 5M of unique source code names, this means 5M keys for source code index) we will still start to get indexing performance deterioration due to limited set of byte buffers available (200M on 32bit jdk).

[xeroxman23]

Hi, is there any chance to see C/C++ plugin open-sourced? So people like me could hack on it and fix annoying issues the plugin has.

[nicity]

Plugin is facade over external C++ executable, so plugin source code is not of very much use.