Learning Rust the hard way - implement B-Tree Index advice?

Hello Good People
I am trying to learn Rust.
The hard way.

I have read The Rust Book now (excellent book, so a tick for RTFM for me!).
I have decided to write a simple in-memory B-Tree Index library - since my background is relational databases so I do know how B-Tree works well enough (and happy to use recursion).

I would like some general direction/approach advice re doing in the Rust idiomatic way.

I am aware of Box, Rc, RcMut and RefCell.

Given the index nodes need to be mutable and owned and manipulated in a graph-like-way (to insert/update/remove/re-balance node key contents), I would like opinions of which Rust features/structs/etc to use to implement this data structure in-memory.

I will get to on-disk persistence/serialization later, I am sure this will be another huge task to get it written in Rust idiomatic way.

Any advice appreciated from a new Rust student!

Many thanks in advance!

A good starting place for this sort of thing is Learn Rust With Entirely Too Many Linked Lists. The book steps you through creating a robust linked-list implementation using both safe and unsafe Rust, but it should be easy enough to extend the concepts to a b-tree as well.

Another resource is rust/src/liballoc/collections/btree/. The standard library source code is freely accessible and normally quite high quality.

One of the original authors of std::collections::BTreeMap wrote up a case study on it, Rust Collections Case Study: BTreeMap. It's a pretty long post, but you get to explore it in a fair amount of detail and the author is quite well renowned around here.

2 Likes

many thanks!