B树

B树

如何选择数据库的数据结构？

两个衡量性能的重要指标:

  1. 读写文件大小
  2. IO次数

树的深度影响IO次数，

  1. 线性表

查找速度：慢

插入删除：插入删除性能消耗高

  1. 哈希表

查找速度：不够快

插入删除：快

缺点：hash表容易产生hash冲突，数据散列不均匀，仍会产生大量线性查询，但相比线性表会好很多。范围查询就需要挨个遍历

image-20240315220328005

  1. 二叉查找树

查找速度：大部分情况很快

插入删除：快

缺点：容易退化成链表，又回到线性查找的速率

image-20240315223243635

  1. 平衡二叉树（AVL）

查找速度：快快快快

插入删除：慢

缺点：查询深度降低，但是插入时增加了查询的时间消耗

image-20240315221607638

  1. 红黑树

红黑树采取宏观的调整，最长子树不超过最短子树的两倍，否则做重新排序：这样相对于avl减小了插入消耗！

查找速度：快快快快

插入删除：快

缺点：虽然他的查找速度很快，而且插入速度也得到了提升，但是随着文件量增多，红黑树深度也会随着变深，依然会增加IO读取次数！

image-20240315221811894

  1. B树

查找速度：快到飞起！

插入删除：快！

舍弃二叉树的概念而选择多子树，有效的降低了树的深度，并继承了树的优点，查询速度很快！

B树结构

本质是多级树，一个节点能存储多个数据，m叉树代表一个节点最多有m分支

关键字：n-1个；子节点则为n

image-20240316103516876

B+树结构

B树效果这么好，还有啥缺点不，怎么优化？

磁盘数据是按页存储的，一个节点的空间占16k，如果节点上还保存了数据内容，那么一个节点能保存的数据key将会大大减少！这会使得IO次数增加

这就不得不提B+树了，B+树的非叶子节点都只保存key和指针，完完全全成为了路标，将key和数据分离了出来，仅仅在叶子结点保存了数据，这样每一页的节点能保存上千条key，提高IO效率，性能非常惊人！

B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：

  • 分支节点的子树指针与关键字个数相同。
  • 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间，这就说明B+树取消了最左边的那个子树
  • 所有叶子节点增加一个链接指针链接在一起
  • 所有关键字及其映射数据都在叶子节点出现。

20200911170432751