二叉树一般用平衡的 AVL 树和红黑树对吧。

那么，相对于这两种树，B+ 树有啥缺点呢？为啥日常编程中，只有在涉及磁盘存储的时候才比较经常看到 B 树？内存里面使用 B 树有什么不好吗？
--
FROM 110.84.121.*

是不是大多数场景，都可以使用 b 树来代替红黑树啊？

【 在 milksea 的大作中提到: 】
: 没啥不好，现代一点的内存容器库就经常用B树了，比如C++的absl就有btree_map，rust标准库用BTreeMap。
: B树在一个块内是线性操作的过程，跨块操作才是对数时间。理论上二叉平衡树需要的都是对数操作数量，总操作数量少；但现代处理器因为缓存的因素，B树的存储局部性更好，实际效率可能更好。
--
FROM 47.243.39.*

最大的缺点就是stl不提供
Google 开源了一个实现，据说比stl::map/set 快
自己搜这篇文章 C++ containers that save memory and time

【 在 hgoldfish 的大作中提到: 】
: 二叉树一般用平衡的 AVL 树和红黑树对吧。
: 那么，相对于这两种树，B+ 树有啥缺点呢？为啥日常编程中，只有在涉及磁盘存储的时候才比较经常看到 B 树？内存里面使用 B 树有什么不好吗？
--
FROM 104.133.9.*

赞，学习了。

我是用b＋搞过fs。说说一些经验吧，高性能存储系统一般增删改查，对元数据操作比较频繁。b＋是把原数据都放在非叶节点，比较紧凑，在空间有限的内存里效率高，空间低。频繁操作的节点还会cache住进一步提升。元数据持久化方面结合log机制，减少频繁的随机访问。

【 在 milksea 的大作中提到: 】
:
: 没啥不好，现代一点的内存容器库就经常用B树了，比如C++的absl就有btree_map，rust标准库用BTreeMap。
:
: B树在一个块内是线性操作的过程，跨块操作才是对数时间。理论上二叉平衡树需要的都是对数操作数量，总操作数量少；但现代处理器因为缓存的因素，B树的存储局部性更好，实际效率可能更好。
: 【 在 hgoldfish 的大作中提到: 】

#发自zSMTH@ALN-AL00
--
FROM 116.30.100.*

红黑树其实是4阶B树。  
  
【 在 hgoldfish (老鱼) 的大作中提到: 】
:  话说，我非常喜欢 b 树的 cow 特性。在添加与删除节点的时候，它都是从叶节点开始，往上不断分裂处理。使用这个技巧，读是不需要加锁的，写才需要加锁。这个对于内存应用，也是非常优秀的特性啊。
:  
:  这么优秀的数据结构，我实在找不到红黑树有哪些应用场景比它强的。
:  
--
FROM 58.38.168.*