B和B+里的B是什么意思?
B是Balanced的缩写，平衡的意思。
全称可以叫多路（多叉）平衡查找（搜索）树。
多路平衡查找树解决了什么问题？平衡二叉查找树为什么不能解决？
由于平衡二叉查找树只有两个分叉，查询叶子结点需要访问$log_2{n}$次节点，即树的高度。
如果要减少查找次数，就要让树变矮一点。
那么一个节点有多个分叉，同时让一个节点存储多个值，就可以降低树的高度，进而减少节点平均的访问次数。
减少节点的访问次数有什么好处？
访问节点的成本可能非常大，减少访问节点的次数，就可以降低总的访问成本。
例如访问IO比访问内存要慢的多，文件系统中普遍采用多路平衡查找树作为存储数据的结构。
B树与B+的区别？
B树与B+共同点：
- 都是一个节点按顺序存储多个值
- 每个节点可以有多个分叉
B树独有：
- 非叶子节点存储了数据，非叶子节点占用空间更大
B+树独有：
- 非叶子节点不存数据只存索引信息，数据全部在叶子节点，非叶子节点占用空间更小
- 叶子结点用双向链表相连，便于顺序查找
B+树作为数据库索引有什么优势？
非叶子结点的大小可以设置为一页，内存从外存读取数据是按页读取的，这样就减少了IO访问次数。
结点内部是有序的，可以再用二分查找去查找元素。
B+树的非叶子结点不存储数据，只存键，这样同样空间大小可以存的键就更多，非叶子结点的数量就会减少，IO访问次数也就变少了。
B+树的叶子结点用双链表链接，这样对区间查询友好，只需要通过非叶结点查找到区间范围，然后顺序遍历即可，可以减少对非叶结点的访问，进而减少IO访问次数。因为由于虚拟内存机制，非叶结点加载到内存后，可能也会被置换到外存，减少对非叶结点的访问次数，也就降低了置换次数，置换是需要IO访问的。