可视化网站
B-Tree的引入
从磁盘查找数据效率低的原因
读写数据越大速度越慢
读写次数越多速度越慢
设计文件查找系统
索引可以提供更快的查询.
哈希表
优点:等值查询比较快
缺点:
- hash冲突后,数据散列不均匀,产生大量线性查询,效率低
- 等值查询可以,但是遇到范围查询,需要遍历,hash不合适
树
树的种类
树 二叉树 BST二叉查找树 AVL平衡二叉树 红黑树 B树 B+树
二叉排序树 BST
插入数据的时候得有序,必须保证:
- 若左子树不为空,则左子树的所有节点的值小于根节点的值
- 若右子树不为空,则右子树的所有节点的值大于根节点的值
问题:
会退化为链表,查询效率降低为O(n).
平衡二叉树 AVL
插入数据的时候保持二叉排序树平衡
左子树和右子树的高度差不能超过1.
问题:用插入的成本来弥补查询的成本,插入效率降低为O(logn),但是查询效率还是O(logn).一旦出现插入操作比查询操作多的情况就不合适了.
红黑树
最长子树不超过最短子树的2倍.
- 性质1 :根节点是黑色的.
- 性质2 :每个红色的节点的两个子节点都是黑色.(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 性质3 :从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点.
相当于不让AVL做大量的旋转操作.
红黑树口诀:左根右 , 根叶黑 . 不红红 , 黑路同.
问题: 当数据特别多的时候,树的深度会很大,就意味着IO的次数会变多,影响读取的效率.
B树
B树就是一个有序的多路查询树.
满足下列要求的m叉树:
- 书中每个节点只多有m个孩子节点(至多有m-1个关键字)
- 每个节节点的结构为:
n代表这个节点有几个关键字.P0第一个子树的地址.k1关键字
例子:m=4的4阶B树
阶数代表单个节点最多有的子节点数量