B树、B+树

目录

一，B树

二，B+树

三，Rust中的B树

一，B树

二，B+树

在实现层面，B树和B+树的唯一区别：

• B树的‌叶子节点和非叶子节点都会存储数据，指针和数据共同保存在同一节点中。‌
• B+树的数据均保存在叶子节点，非叶子节点只存储索引信息。‌

三，Rust中的B树

rust的std中没有专门的B树，而是直接给出了基于B树实现的Map:

pub struct BTreeMap<
    K,    V,    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
> {
    root: Option<Root<K, V>>,
    length: usize,
    /// `ManuallyDrop` to control drop order (needs to be dropped after all the nodes).
    pub(super) alloc: ManuallyDrop<A>,
    // For dropck; the `Box` avoids making the `Unpin` impl more strict than before
    _marker: PhantomData<crate::boxed::Box<(K, V)>>,
}

root应该就是B树的根，相应的操作直接基于BTreeMap去定义实现。