如果我要用b树实现内存中(RAM)搜索操作，那么与二叉树相比，在缓存或其他一些效果方面会更好吗？
我所知道的是-
binary search tress---O(log n)
btrees ---------------O(c log n)
最佳答案
算法复杂度是相同的，因为O(logb n)= O(c log n)= O(log n)，但是隐藏在big-O表示法中的常数因子可能会显着变化，具体取决于实现方式和硬件。
B树设计用于磁盘硬盘，具有很大的访问时间(将磁头移动到适当的位置)，然后读取整个物理扇区。使B树节点与扇区一样大可以最大程度地减少访问次数，并使每次读取操作中的有用数据最大化。
但是，如果您的内存不足，则访问时间可以忽略不计，因此更好的比较方法是计算算法访问的单个单词的数量。
例如，让我们计划一个数据结构来存储220个密钥，每个密钥1个字，在32位计算机上总共存储4MiB的原始数据。
二进制搜索树将具有220个节点，每个节点拥有一个键和两个指针(3个单词)。深度将为log2(220)=20。平均搜索将必须从其路径中的每个节点(从根开始一直向下)= 40个单词读取密钥和指针之一。
用于硬盘的B树将具有4kB节点。每个节点可以在内部存储为键和指针对的排序数组，在其中256和512之间。平均搜索会是什么样子？考虑平均3/4填充，每个节点将包含384个条目，并且其内部二进制搜索将必须平均访问log2(384)= 5.95键。平均深度将为log384(220)= 2.33，因此我们的搜索将平均需要读取2.33乘以5.95键，或大约 14个单词。
在低扇出(分支因子)B树的情况下，每个节点保持16至32个键，平均填充将为24个键，平均深度log24(220)= 4.36，在每个节点中进行二进制搜索将进行log2(24)= 4.58的比较，整个平均搜索将不得不阅读 20个单词。
请记住，最后两个数据结构比二叉树获得更好的结果，因为它们通过修改来优化读取操作。要将密钥插入这些B树之一中，您平均必须重写整个384字或24字节点(如果不超过一个)，而在二叉树的情况下，写操作仍只需要最多触摸40个字。
(以前我错了。感谢@virco和@Groo指出了我在评论中的错误。)
无论如何，似乎只有内存的B树具有低扇出appear to perform better than binary trees in practice。
对于当前的32位和64位体系结构，每个节点32个密钥似乎是一个最佳选择。许多较新的语言和库都使用32键B树作为内置数据结构，内置数据结构，或将其替换为哈希表和数组。这种用法是由Clojure和其他功能语言带头的，但后来被更主流的语言(如Javascript)所采用，最近的重点是不可变数据结构(例如Immutable.js)。
不仅可以通过计算从内存中读取的字数来说明该结果，还可以通过缓存未命中来解释缓存的丢失，这是导致CPU停顿并等待RAM的读取操作。如果缓存体系结构一次可以获取包含整个B树节点的RAM块，那么我们将获得与成功用于基于磁盘的大容量存储相同的优化。
对于硬盘优化的数据结构，我们将使用B树，其节点的大小与物理磁盘扇区一样大，以最大程度地减少磁盘访问时间。在这种情况下，我们使用B树，其节点的大小与3级缓存针对RAM所执行的读取操作一样大，以最大程度地减少缓存未命中。
关于performance - B树与二叉树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6211118/