Re:Show HN: A first project in Rust – in-memory order book
by globular-toast on Saturday February 22, 2020 @05:07AM
(#22390228)
Why a B-tree if it's supposed to be in-memory? A heap would be easier to implement and more efficient.
[ Parent
| on HN ]
Re:Show HN: A first project in Rust – in-memory order book
by evdubs on Saturday February 22, 2020 @06:22AM
(#22390450)
Rust provides a built in B-tree[1] and it offers this over a binary search tree to avoid pointer chasing. With respect to heaps, are you thinking that a BinaryHeap[2] could be used here? I don't see how such a structure allows you to arbitrarily remove/update orders in the book. Looks like you can just insert arbitrary orders by price (using push(x)) and then get the best bid or offer (using pop()). Am I missing something? If the API was changed to be more like a binary search tree, you don't think the pointer chasing would reduce performance for larger books?
[1] https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...
[2] https://doc.rust-lang.org/std/collections/struct.BinaryHeap....
Re:Show HN: A first project in Rust – in-memory order book
by globular-toast on Saturday February 22, 2020 @05:06PM
(#22393647)
I missed the fact that it was supposed to be more than just a priority queue. I would have said binary search tree instead of heap, but it makes sense now I know that B-tree is built in.