B树与二叉树

Question

如果我使用b树实现内存(RAM)搜索操作,那么与二叉树相比,它在缓存或其他一些效果方面会更好吗？

我所知道的是

binary search tress---O(log n)
btrees ---------------O(c log n)

在各种博客上有很多关于这方面的讨论.

Answer 1

算法复杂度是相同的,因为O(log _b n)= O(c log n)= O(log n)但是隐藏在big-O表示法中的常数因子可能会有明显的变化,具体取决于实现和硬件.

B树被设计用于盘片硬盘,其具有大的访问时间(将头部移动到位),之后读取整个物理扇区.使B树节点与扇区一样大,最小化访问次数,并使每次读取操作中的有用数据最大化.

但是,如果您的内存不足,则访问时间可以忽略不计,因此更好的比较是计算算法访问的单个单词的数量.

例如,让我们计划一个数据结构来存储2个^20个密钥,每个密钥为1个字,在32位机器上总共有4MiB的原始数据.

二叉搜索树将有2 ^20个节点,每个节点包含一个键和两个指针(3个字).深度将是log ₂(2 ²⁰)= 20.平均搜索将必须读取密钥和其路径中每个节点的一个指针,从根一直向下= 40个单词.

为硬盘制作的B树将具有4kB节点.每个节点可以作为键和指针对的排序数组在内部存储,在256和512之间.平均搜索结果是什么样的？考虑到平均3/4填充,每个节点将包含384个条目,并且其内部二进制搜索将必须访问平均log ₂(384)= 5.95个密钥.平均深度将为log ₃₈₄(2 ²⁰)= 2.33,因此我们的搜索必须平均读取2.33倍5.95键,或大约14个单词.

在低扇出(分支因子)B树的情况下,每个节点保持在16和32个键之间,平均填充将是24个键,平均深度log ₂₄(2 ²⁰)= 4.36,二进制搜索每个节点将进行log ₂(24)= 4.58比较,并且整体平均搜索将必须读取大约20个单词.

请记住,最后两个数据结构比二叉树获得更好的结果,因为它们优化了对修改的读取操作.要将密钥插入其中一个B树中,您必须平均重写整个384字或24字节点(如果不超过一个),而在二叉树情况下,写操作仍然只需要最多可达40个单词.

(以前我错了.感谢@virco和@Groo在评论中指出我的错误.)

在任何情况下,似乎具有低扇出的仅存储器的B 树在实践中似乎比二叉树表现更好.

特别是每个节点32个密钥似乎是当前架构(32位和64位)的最佳选择.许多较新的语言和库使用32键B树作为内置数据结构,同时或作为哈希表和数组的替代.这种用法由Clojure和其他函数式语言引领,但随后被更多主流语言(如Javascript)所采用,最近关注的是不可变数据结构(例如,Immutable.js)

这个结果不仅可以通过计算从存储器读取的字数来解释,而且缓存也会错过,这些读操作会导致CPU停顿并等待RAM.如果缓存体系结构可以一次获取包含整个B树节点的RAM块,我们将获得与基于磁盘的大容量存储成功使用的相同优化.

在硬盘优化数据结构的情况下,我们将使用具有与物理磁盘扇区一样大的节点的B树,以最小化磁盘访问时间.在这种情况下,我们使用B树,其节点与由Level 3高速缓存对RAM执行的读取操作一样大,以最小化高速缓存未命中.

Answer 2

B树与二叉树的不同之处在于,键和指针聚集在内存中,因此在磁盘和内存中都可以获得更好的缓存行为.但是,渐近(big-O)运行时没有区别.