Research: Explanation needed for the tree data structure used in Slab

[secretshardul]

What I understand till now is that is a binary tree is used to store bid/ask data:

1. Inner nodes can have upto 2 children (hence binary). Children can either be other inner nodes or leaf nodes.
2. Leaf nodes represent orders and store data such as owner and quantity.
3. The key attribute is used to order nodes. It is present in both inner and leaf nodes. It begins with 0 for at the root node and grows sequentially.

Questions:

1. What data structure is this exactly? I'm not sure if it's a binary search tree. The key attribute used for arrangement doesn't seem to be coming from placed orders. Also it arbitarily begins from 0.
2. What does the structure optimize?
3. Why custom implementation instead of a cargo crate?

[dafyddd]

I'm not the person who built it but here are some answers:

1. It's a critbit tree which is a type of patricia tree. The first 8 bytes of the key attribute is the price and next 8 bytes are the seq num. Together they represent price-time priority and can be used to sort for that reason
2. I think the structure is a good tradeoff between speed and space usage.
3. cargo crates will usually use dynamic memory but this tree needs to live on a static size slab of bytes that's on chain