implement a B-tree

[thestinger]

A B-tree stores sorted arrays of a chosen size instead of lone nodes, so it can be much more cache-friendly than a red-black tree when used with small key/value types. The size will just have to be hardcoded for now since it can't be part of parametrizing it.

[duckmatt]

Hi, I'd like to give this an attempt, is this going to be treemap.rs reimplemented as a B-tree?

[thestinger]

@duckmatt: yeah, it would just expose the same interface as treemap

it could start off as another module and eventually replaced the treemap module

[duckmatt]

Just to give an update, I haven't disappeared. I'm hoping to get the btree fully functional and uploaded to my github this weekend or next, then the week or so after adapt to the treemap interface, been slow progress as I'm learning the language at the same time :p

[duckmatt]

I tried to get a btree working with owned boxes for the nodes, but found it can't work as I need to maintain a list of mutable nodes whilst walking down the tree. Seems the way around this is to either restrict the tree to use an even order, which I guess wouldn't be a problem if the order is always going to be fixed, or use reference counting for the nodes, which i assume will make it a bit less efficient. What would you go for between these?

[alexcrichton]

@duckmatt the general trend for containers in the standard library has been to avoid @ as much as possible. It forces users of the containers to have GC turned on, which may not always be desirable. If you can avoid @, then definitely do so!

[smvv]

I'm working on a b-tree implementation as well. @duckmatt Perhaps we can combine our efforts and work together on the implementation?

My implementation is nowhere near complete. At the moment, the insert method does split the node when the node is full. However, the node is not properly inserted into its parent node. See test_insert_split_add_root() for a test case that currently failed because of this.

I think I chose a proper data structure layout to start with:

• separate keys from leaf/node pointers to speed up key matching.
• there are n nodes and n - 1 keys. With key-value pairs (where value is a node- or value pointer), it is not possible to have n-1 keys. Having n keys implies that the key has to be copied, or is set to None. I thought that an extra key in every node would be wasteful, if the data structure layout is also possible with n-1 keys.
• trees are owned and there are no copies of keys or values necessary during the insert.
• stack-allocated, fixed-sized vectors to store the keys and node-/value pointers.

At the moment, BTREE_ORDER is a constant. There was a discussion on IRC about if it was possible to make it a trait parameter, but that's not possible with the current Rust compiler.

Comments are more than welcome. I started this b-tree implementation as an exercise to learn Rust, but I think we could turn our efforts into a usable b-tree implementation suitable for the Rust standard library.

Source: https://github.com/smvv/rust-btree/blob/master/btree.rs
Docs: http://smvv.io/rust-btree/doc/

@duckmatt Btw, my nickname is smvv on the Rust IRC channel #rust.

[duckmatt]

@smvv Looks good, that's pretty much where I got to so I figure I'll just make contributions to your code from now on and we can try to get that working.

Inserting into a parent is where I found the problem to be, because if the parent is full too then you need to split the parent, then insert into the parent of the parent, and so on until you reach the root or a node that's not full. So to implement this it seems like you need to build a list of mutable nodes as you walk down the tree, you'll add to this every time you come across a full node and clear it each time you come across a not full node. Problem is with this approach you then end up with two mutable reference to the same owned box. The alternative is to either use some interesting flow of data with recursion if it's possible, or to do the splits while walking down the tree (which is only possible with an even order, but I see you're asserting for that already anyway, so this may be the way to go)

[smvv]

TreeMap uses a recursive approach: https://github.com/mozilla/rust/blob/master/src/libextra/treemap.rs#L589 I think a top-down algorithm would be useful indeed.

[smvv]

The b-tree successfully inserts 100,000 randomly generated uints, and checks if the key is in the tree at the end. Inserting 100,000 uints followed by 100,000 lookups takes 50 ms on an intel i7 950 at 3.07 GHz. Without the lookups, inserting 100,000 uints takes 40ms. At the moment, removing keys is not implemented, and the b-tree will fail if a duplicated key is inserted (see below).

It is important to note that the insert() method does not return true / false for a new / old key. The reason is that the top-down algorithm cannot determine if a key does already exist. If a key is stored in a leaf, the top-down algorithm will discover the uniqueness once it's at the leaf node. However, in order to insert something in a leaf, the top-down algorithm has to split full nodes before it is at the leaf.

The question is whether it is useful to return true for a new key that is not inserted before. If it is important, insertion has to perform a find() prior to the splitting. How about defining two methods: one that performs a find() operation for uniqueness prior to insertion, and one for inserting only unique values?

@thestinger @duckmatt What is your opinion about this?

I chose 20 as minimal degree for the b-tree. It gave a good result for inserting 100,000 and 1,000,000 random uints. I compared it with 40 and 50, but insertion took longer (plus ~10ms for 100,000) for those values. I'm not sure what the optimal value will be.

This top-down algorithm is used: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap19.htm

Source: https://github.com/smvv/rust-btree/blob/master/btree.rs

[duckmatt]

@smvv What I was doing in my implementation was the search to find where in the current node the position of the child to walk down to was before splitting, I did this with a binary search that returned an enum of either Match(position) or NoMatch(position), position = closest key if it's not a match, if it's a match then I knew it already existed. The thing is, the way I see it you would have to do this search anyway, as you would need to know where in the split nodes to walk down to/insert the new key/value into

Here's the bsearch I made if it's of any use: https://github.com/duckmatt/rustbinarysearch/blob/master/bsearch.rs

[smvv]

I did this with a binary search that returned an enum of either Match(position) or NoMatch(position), position = closest key if it's not a match, if it's a match then I knew it already existed.
The thing is, the way I see it you would have to do this search anyway, as you would need to know where in the split nodes to walk down to/insert the new key/value into

I'll give it a try, because I think that would be possible indeed. While walking down, you can find the key in a internal node or a leaf. There should be no need for a second find operation. Although, it will cause a split operation on a node when the node is full, and the key exists already in the b-tree. This is not really an issue because the properties of the b-tree still hold.

Your comment gave me another idea: The b-tree uses binary search for finding a leaf, but it does a linear search on the keys in a node. As an experiment, I used binary search on the keys in a node to see if binary search is faster than linear search. The idea behind the experiment is that the run-time increases when the number of keys per node increases. Unfortunately, using binary search on the keys did not reduce the run-time. I tried larger number of keys as well (# of keys I tried is {20, 40, 50}).

You can find the disabled binary search here: https://github.com/smvv/rust-btree/blob/master/btree.rs#L142

And important to note is: Using btree.rs as a library does not work: see #8044.

[thestinger]

@smvv: You could try using a galloping search instead. You search by stepping forwards by N where N doubles every time (accessing the indices 0, 1, 3, 7, 15, ...) until you overshoot, and then do a binary or linear search over the range from the last step.

[thestinger]

Also, a linear growth pattern might end up being faster (accessing 0, 1, 3, 6, 10, 15) since the fanout size is a known, small constant.

[davidhalperin]

@smvv Your structure doesn't seem right to me at a glance. A B-Tree typically stores both values and children in internal nodes. A B+ Tree stores either values or children but requires copying keys and you have claimed that you are not doing so. I haven't analyzed this in great detail so it may or may not work and may or may not have good properties but it doesn't seem to be textbook.

I'd also like to give this a try and have a very different representation in mind. Would anyone object if I gave this a try in parallel? I don't want to steal anyone's thunder.

The representation I have in mind is here. Nice things about this are:

• Things that we know are there aren't wrapped in options.
• The invariant that there's always one more branch than key/value is enforced by the type.
• Leaves are compact and fast to iterate through.
• Size of the nodes is tunable in the constructor.

The main cons I see are:

• Keys in branches are relatively far apart might be slower to scan.
• 2 allocations in each branch node.
• Special case for dealing with the far right child of a branch.

[duckmatt]

@davidhalperin The problem I see with the b+tree here is that you're going to have two references to an owned box, the right pointer will be pointing to a node that's already owned by a vector. Or are those nodes in the vectors not owned boxes? I'm getting a feeling that's where I went wrong