红黑树B树B+树

红黑树B树B+树

Scroll Down

红黑树B树B+树

二叉查找树

二叉查找树性质

  • 子树上所有结点的值均小于或等于它的根结点的值。
  • 子树上所有结点的值均大于或等于它的根结点的值。
  • 左、右子树也分别为二叉排序树。

二叉查找树删除一个节点

  • 删除节点存在右子树,则使用右子树的最左子节点进行替换,然后递归的向下删除
  • 删除节点存在左子树,则使用左子树的最右字节点进行替换,然后递归的向下删除

红黑树

红黑树和AVL树区别

  • AVL树是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1)。不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡。所以AVL树适合用于插入与删除次数比较少,但查找多的情况。
  • 红黑树是弱平衡二叉树,它通过着色限制的关系,确保没有一条路径会比其它路径长出两倍,相对于AVL树来说,它的旋转次数少,所以对于搜索,插入,删除操作较多的情况下,我们就用红黑树

(建议没学AVL树就别扯这个,别人深入问为什么红黑树好是答不上的)
红黑树的性质(必背,面试必问必介绍):

  • 红色结点不可能相连,黑色节点可以相连
  • 根节点是黑色节点
  • 每个红色节点的两个子节点都是黑色,叶子节点都是黑色(Null节点)
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
  • 插入的点默认都是红色

左旋
左旋的理解不要纠结于字面记忆,只要记住向左旋转,记住它的动态过程,自己旋一下

右旋
千万别死记步骤,记动态过程,留下根深蒂固印象

插入规则
插入的过程是递归向上检查并变换的过程,并不是插一个节点变化一次。
变颜色

  • 当前结点的父亲是红色,且它的爷爷结点的另一个结点(叔叔)也是红色:
    • 把父结点设为黑色
    • 把叔叔结点设为黑色
    • 把爷爷结点设为红色
    • 把指针定位到爷爷节点继续往上分析变换规则

左旋

  • 当前父节点是红色,叔叔是黑色的时候,且当前的结点是右子树,左旋以父结点作为左旋

右旋

  • 当前父结点是红色,叔叔是黑色的时候,且当前节点是左子树:
    • 把父点变成黑色
    • 把爷爷节点变成红色
    • 以爷爷节点进行右旋

以XX节点进行左旋/右旋,XX节点对应着E节点
红黑树插入删除实例 红黑树的删除很复杂,面试的时候只介绍上面规则,剩下就说不懂?

B树

select * from user where user_id=100 # 索引查找
select * from user where user_id<100 and user_id>0 # 范围查找
select * from user where user_id = 100 and name = "赵云" # 联合索引查找

M阶Btree的性质:

  • 结点最多含有m颗子树(指针),m-1个关键字(存的数据,空间)(m>=2)
  • 除根结点和叶子结点外,其他每个结点至少有m/2(向上取整)个子节点
  • 若根节点不是叶子节点,则至少有两颗子树

插入规则
B树插入教学+例子

B+树


B+树特点

  • 叶子节点用指针连在一起形成双向链表
  • 非叶子节点仅用作索引,子节点存储数据,它的非叶子节点和叶子节点有重复元素
  • 概要,关键字和Key值,数据存储的地方,双向链表

附带知识
树的阶数M
磁盘页大小16K/字段。为了尽可能地利用连续空间,一次刚好能全部拿出一个节点的数据
data块存储内容

总结

Hash
mysql是提供了BTREE和HASH的索引方法

  • 优点:查询性能快,只需要O(1)定位时间,只适用于等值查询
  • 缺点:
    • 无法进行范围查询
    • 重复键会造成哈希冲突,影响性能

二叉查找树

  • 优点:查找性能快,O(logn)
  • 缺点:不平衡情况下会退化为链表 O(n)

时间复杂度为log(n) ,n为节点。(计算公式:时间复杂度为树的高度x:2^x=n>>x=logn)
红黑树

  • 优点:保证了不会出现不平衡情况,适合用于内存型数据结构(为什么hashmap用红黑树)
  • 缺点:
    • 索引是存储在磁盘文件上,磁盘上的存储是随机存储,每次都需要转圈去读取一个节点,这样当树的深度过大而造成磁盘IO读写过于频繁,进而导致效率低效的情况
    • 磁盘每次读取是读一页,一页只是为了获取一个节点的数据,也会造成性能浪费

B树

  • 优点:
    • 一个节点存储多个数据,更好的利用磁盘页的大小
    • n叉树树的高度降低,磁盘读取次数降低
  • 缺点
    • 非叶节点存储数据,查询效率不稳定
    • 非叶节点存储key和data指针,导致一个节点内能存的key数量降低,导致树的高度增高
    • B树不适合做范围查询,必须用中序遍历的方法按序扫库

B+树

  • 优点:
    • 叶子节点用指针连在一起形成双向链表,增加了遍历的高效性
    • 非叶节点不带数据,可以更高效使用索引空间
  • 缺点:
    • B+树的数据只出现在叶子节点上,单次查询性能不如B树

mysql使用B+树,mongo使用B树所以B树不是一无是处。
引用一篇博文中网友评论的一段话:

数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题,B+树应运而生。
B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操