B树:
1. B树中每个节点最多有m个孩子,称为m阶B树。
2. 根节点至少有两个孩子。
3. 所有的叶子节点都位于同一层。
B树的目的是让每一个索引块尽可能存储更多的信息。与平衡二叉查找树不同,B树主要是为优化大块数据的读写操作而设计的。普遍应用在数据库和文件系统。
B+树是B树的一种变体:
1. B+树中的节点指针数目与关键码的数目相同。
2. 跟记录有关的数据均位于叶子节点中,非叶节点仅具有索引作用。
3. 树的所有叶节点构成一个有序链表,可以根据关键码的排序次序遍历全部记录。
数据库为什么选择B+树索引?而map使用红黑树索引?
因为外存(磁盘)和内存差异。数据库的查询是在磁盘中,读取到数据之后存储在索引结构中。磁盘每次读取的最小单位是一簇。
而map位于内存中,可以按位读取。
红黑树是二叉树,在数据库中使用红黑树会使得索引过于庞大。而内存中需要进行频繁的插入操作,如果使用B+树则修改量会很大。
原文:https://www.cnblogs.com/conanpeng/p/12806249.html