给你一组数，最自然的效率最低的查找算法是顺序查找——从头到尾挨个挨个遍历查找，它的时间复杂度为O(n)。
而另一个大家都知道的，效率很高经典查找算法——二分查找法，它的时间复杂度是O(logn)。但二分法的数据结构是数组，这样才能通过公式 (low+height)/2=middle计算出中间位置的元素。而数组的修改效率很低，最坏的情况下，插入一个元素，要移动n个元素。
通过模拟二分查找法的插入、查找过程，会发现和二叉平衡树很相似，那我们分析一下二叉平衡树。简单的二叉树无法保证能保证查找的每一步节点是二分法中的中间位置，最坏情况会蜕变为顺序查找。所以需要对二叉树进行调整，让它变成二叉平衡树，这样查找的效率就能保证了，二叉平衡树的查找时间复杂度也是O(logn)。但是二叉平衡树的缺点在于，调整的消耗很大。它的每次插入，都要一层一层往上确认、调整。
我们再来看另外一个二叉查找树——B树。观察一下B树的插入过程。
可以看到，只有在插入后键值数超过最大键值数时，才会去修改父节点。如果父节点的中的键值数没有超过最大键值的话，就不会去动祖父节点了。所以B树的调整效率比二叉平衡树更高。
B树的另一个很大的应用是查找放在磁盘中的数据，比如数据库中数据的查找。假设现在有1G的数据，这么大的数据肯定不可能放在内存中，必须持久化到硬盘中。假设有100W条数据，使用二叉平衡树的话树高为20，即最坏情况下要进行20次I/O。如果使用64阶B树，即最坏情况下也只需要进行4次I/O就能完成查找。这就是为什么涉及到硬盘I/O的查找数据结构一般都会考虑B树。
我们常听到的红黑树，它的本质其实就是对概念模型：阶数为4的B树——”2-3-4树”的一种实现。由于直接进行不同节点间的转化会造成较大的开销，所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3-4树中不同的节点。
B+树是B树的一种变形形式，和B树的区别在于：
MySQL的存储引擎InnoDB就采用B+Tree的数据结构存储索引。B+树相比于B树的优点是：
Original: https://www.cnblogs.com/daheww/p/16213521.html
Author: daheww
Title: 各种查找算法的选用分析（顺序查找、二分查找、二叉平衡树、B树、红黑树、B+树）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/575198/
转载文章受原作者版权保护。转载请注明原作者出处！