tk网站免费,拨付网站建设经费的请示,房产中介如何找客源,培训教育“mysql中常用的数据库搜索引擎InnoDB,其索引通过BTree的方式进行构建。”
实在想不起来BTree是怎么一回事了。以点带线#xff0c;将涉及到的数据结构一起复习一下。 文章目录 数据结构定义红黑树定义使命 BTree定义使命 BTree定义 InnoDB BTree 旋转与调整二叉排序树插入删…“mysql中常用的数据库搜索引擎InnoDB,其索引通过BTree的方式进行构建。”
实在想不起来BTree是怎么一回事了。以点带线将涉及到的数据结构一起复习一下。 文章目录 数据结构定义红黑树定义使命 BTree定义使命 BTree定义 InnoDB BTree 旋转与调整二叉排序树插入删除 平衡二叉树插入 删除红黑树插入删除 m阶BTree插入删除 m 阶BTree插入删除 参考内容 数据结构定义 数据结构 定义二叉树每个节点最多有两个子树二叉排序树又叫二叉搜索树。在二叉树的基础上递归定义 任意子树根节点大于其左子树最大值小于右子树最小值. 左根右平衡二叉树在二叉排序树的基础上 递归定义 任意节点 左右子树的高度差≤1.红黑树在二叉排序树的基础上递归定义 见下方BTreeB-Tree 同一个东西。见下方BTree见下方
如果插入的是有序序列 二叉排序树的效率降低为O(n). 所以推出 平衡二叉树
红黑树
定义
左中右 前提是一棵二叉搜索树左中右根、叶黑 根节点和叶子结点都是黑色不红红 不存在两个红色节点有直接父子关系黑路同 任意节点到所有叶子节点经过的黑色节点数相同
使命
红黑树并不是在平衡二叉树的基础上定义的。
由于平衡二叉树左右子树高度差≤1要求过于严格。虽然查询效率较高但插入、删除时调整频繁 因此引入红黑树。
由于不红红和黑路同的性质可以推断出:红黑树左右子树最长路径节点数不超过最短路径的2倍。
相对于平衡二叉树插入、删除效率有所提升。
BTree
BTree 就是多路查找树一个节点内可以有多个元素每个元素都有左右子树。 2阶BTree 退化成平衡二叉树
定义 有序 1. 结点元素内有序 2. 元素的左子树都小于它,右子树都大于它 平衡 所有的叶结点都在同一层 节点限制 m阶BTree 根节点至少有1个元素2个分支 其他节点 至少有(m1)/2个分支 (m-1)/2个元素左右间隙肯定要比元素数多1 所有节点元素数m, 分支数≤m。 所有叶子节点在同一层上
使命
数据是存储在磁盘上每次将节点读入内存就需要一次IO操作IO操作是比较耗时。树的高度限制了数据的查找效率。
一次IO读取连续地址的多个字节和读取一个字节几乎没有什么差别。
通过增加节点元素数降低树的高度 就成为了必然的选择。
一个节点可以有多个元素 每个元素左右间隙指向后续节点。将左右间隙视为左右子树。
BTree
定义
从BTree基础上发展而来
非叶子结点直接存储索引左子树最大值右子树最小值叶结点包含全部关键字及指向相应记录的指针非叶结点只作索引所有节点元素数m(也有地方说是m), 分支数≤m每一个叶子节点都有指向后续叶子节点的指针 InnoDB BTree
对经典BTree进行改造除了记录叶子节点的头部位置后续叶子节点外 记录了前驱节点。提升了中序遍历和范围查找效率。
旋转与调整
二叉树就是为了阐述的需要没有实际应用的意义不存在调整的问题。
二叉排序树
插入
与当前节点比较 小于当前节点在左子树进行比较 大于当前节点在右子树进行比较。 最后插入到叶子节点上。
Insert 4 2 3 1 删除
通过比较查找定位到待删除的节点 叶子节点,直接删除 只有左子树或只有右子树 删除后让子树占据其位置 左右子树都有 需要进行转化 让其中序遍历前驱节点或后继结点占据其位置转化为删除中序遍历前驱节点或后继结点。转化为前两种情况。 演示一下删除节点50的过程 节点50左右子树都有使用中序遍历定位后继节点。将节点65放到节点50的位置待删除的节点只有右子树 将右子树直接挂上
平衡二叉树
插入
通过递归进行节点比较插入到叶子节点。 然后判定是否出现左右子树高度差1的情况。 没有出现 插入结束。否则根据下面四种情况进行调整
类型调整方式LL爷爷节点顺时针旋转右旋RR爷爷节点逆时针旋转左旋LR父节点逆时针旋转,爷爷节点顺时针旋转右旋RL父节点顺时针旋转,爷爷节点逆时针旋转左旋 所有的旋转都是绕着直接子孩子进行的旋转。 调整之后 高度-1. 调整完成。
删除
分为两个过程
删除 删除方法与二叉搜索树相同调整 找到层级最低靠近叶子节点失衡的节点C然后确定类型和调整方式 找到C层级更深的子树A. 找到A层级更深的子树B. AB对应上面的LL、RR、LR、RL四种情况然后进行调整。
这里面有一种特殊情况 B不存在A的左右子树深度一致 如果是L型(A是左子树)进行顺时针旋转.如果是R型进行逆时针旋转。 红黑树
插入
红黑树的插入容易违反根叶黑和不红红的特性。
新插入的节点定义为红色
分下面几种情况进行讨论
1. 新插入节点是根节点 直接变黑 调整完成
2. 新插入节点的父节点是黑节点 不需要调整
3. 新插入节点的父节点是红节点 违反不红红的特点参照下面的方法进行调整。2.插入的是红色节点 父亲是红色节点 如果叔叔是黑色违反黑路同 如果叔叔为红色不能有子节点红色违反不红红黑色违反黑路同 叔叔节点 调整方式R叔叔节点R-B, 父亲节点R-B,爷爷节点B-R, 从爷爷开始继续调整不违反根叶黑、不红红就完成不存在或者为黑色节点插入节点、父节点、爷爷节点 根据LL\RR\LR\RL进行旋转调整 变换后设置新根节点(三个节点中)为黑色其他2个节点为红色.
来一个插入演示。 Insert 34、23、15、10、13、14、35、36. 删除
红黑树删除容易破坏黑路同的性质。
通过节点比较 定位到要删除的节点
与二叉搜索树一样如果左右子树都有 转化为中序遍历直接前驱或者直接后继将节点内容用直接前驱或直接后继的值进行代替 转化为对叶子节点或者单子树的删除。
叶子节点可能为红或者黑 单子树只可能为黑色节点下面挂一个红色节点。
待删除节点为红色叶子节点直接删除 待删除节点有单子树将红色节点挂到子树上变成黑色。
待删除节点为黑色叶子节点较为复杂
兄弟节点颜色兄弟节点有红孩调整方式B有待删除节点变成双黑节点 根据其类型参照下面表格进行旋转变色。B无兄弟变红 双黑节点可以理解为-1黑节点上移到父节点R无兄父变色 然后父节点绕兄弟节点旋转 双黑节点继续调整
双黑节点碰到红色节点 Red-Black 调整结束。 双黑碰到根节点 直接变成黑节点 调整结束。 双黑节点碰到兄弟节点是null调整结束。
删除节点为黑色节点兄弟节点为黑色节点兄弟至少有一个红孩
表格中的孩子指的是兄弟的孩子父节点指的是当前节点的父节点当然也是兄弟父节点
变色和旋转情况如下 兄弟 兄弟左孩子 兄弟右孩子 类型变色与旋转左子树R-LL左孩子R-B, 兄弟节点变成父节点颜色 父节点变黑。 然后进行旋转右子树-RRR右孩子R-B, 兄弟节点变成父节点颜色 父节点变黑。 然后进行旋转左子树B或者nullRLR右孩子变成父节点颜色 父节点变黑。 然后进行旋转右子树R-RL左孩子变成父节点颜色父节点变黑。 然后进行旋转
删除顺序 17 15 13 34 25 23 18 27 37 10 9 6 m阶BTree
插入
所有直接的插入都在叶子节点进行(从根节点定位到叶子节点)
1. 只有一个元素作为根节点
2. 从根部进行比较 跳转到叶子节点后 进行插入。
如果节点元素数m, 需要进行分裂。 m/2位置元素上移 以该元素作为分界点将一个节点拆分为两个节点。然后将比较节点m/2位置元素移动到父节点。 继续判断父节点是否发生上溢 继续进行调整。m 3 插入序列 27 14 18 36 70 3 17 20 23 34 45 53 58 84 删除
定位到要删除的元素如果发生在非叶子节点 将中序遍历直接前驱或直接后继进行替换。 修改为删除直接前驱或直接后继节点
删除后节点元素数 (m-1)/2,结束. 如果(m-1)/2,寻找左兄弟节点或者右兄弟节点进行借元素。 寻找左兄弟借元素 左兄弟 最大值上位 父节点里面的父元素移动到节点左侧。 寻找右兄弟借元素 右兄弟 最小值上位 父节点里面的父元素移动到节点右侧。
如果左右兄弟都不够借 就与左兄弟或右兄弟合并。 与左兄弟合并的时候 父节点的父元素下移到左兄弟然后当前节点所有元素合并到左兄弟节点右侧。 此时 如果父节点发生向下溢出对父节点继续调整 否则调整结束。
m3 最小节点数 (3-1)/2 1 不存在向下溢出的情况了 这里使用m5.进行演示 84 36 90 58 70 53 34 27 45 21 20 23 17
m 阶BTree
BTree所有元素都保存在叶子节点 插入都发生在叶子节点进行分裂时 分裂点左侧断裂 向上copy一份中间元素。 左侧指向的索引节点小于当前索引值右侧当前索引值
叶子节点有指向中序遍历后续叶子节点的指针。
插入
m 5.
插入序列 27 14 18 36 70 3 17 20 23 34 45 53 58 84 90 删除
删除非索引节点时直接删除。 发生向下溢出左右可以借的话 进行左右借位。借位后索引修改为借到元素并将该元素合并过去 如果不够借进行作用合并注意索引的调整。 以及可能发生的父节点向下溢出。
删除序列
53 36 34 20 58 70 20 84 14 27 45 18 参考内容
B站蓝不过海呀数据结构教学视频 旧金山大学数据结构可视化工具
