平度市城市建设局网站,在网站建设中 为了防止工期拖延,怎么做网站滑动图片部分h5,做教务网站的需求分析1.AVL平衡二叉树底层原理 背景 二叉查找树左右子树极度不平衡#xff0c;退化成为链表时候#xff0c;相当于全表扫描#xff0c;时间复杂度就变为了O(n) 插入速度没影响#xff0c;但是查询速度变慢#xff0c;比单链表都慢#xff0c;每次都要判断左右子树是否为空 需…1.AVL平衡二叉树底层原理 背景 二叉查找树左右子树极度不平衡退化成为链表时候相当于全表扫描时间复杂度就变为了O(n) 插入速度没影响但是查询速度变慢比单链表都慢每次都要判断左右子树是否为空 需要保证二叉查找树一直保持平衡就需要用到平衡二叉树 平衡二叉树 称为AVL树Adelson-Velskii和Landis平衡二叉查找树是一种特殊的二叉查找树每个节点的左右子树的高度差不能超过1。平衡二叉树保证了树的构造是平衡的当插入或删除数据导致不满足平衡二叉树不平衡时会进行调整树上的节点来保持平衡。 平衡二叉树的插入和删除操作都是O(logn)的因此它的查找性能很高比非平衡的二叉查找树要快得多。 实现方式红黑树、 Treap、伸展树等。 核心思想 在插入或删除节点时如果发现子树不平衡则对子树进行旋转操作使其重新达到平衡 旋转操作有三种哪边高度底就哪边旋转 提升高度 左旋LL旋转右旋RR旋转左右LR双旋 和 右左RL双旋 图解过程 问题点 查找操作 二叉搜索树的时间复杂度介于O(log2N)到O(n)之间如果退化成单链表时间复杂度就是顺序查找为O(n)如果是平衡二叉树查找效率会提高到O(log2N) 例子 平衡二叉树的高度就等于每次查询数据时磁盘 IO 操作的次数。假如磁盘每次寻道时间为10ms在表数据量大时查询性能就会很差1百万的数据量log2(N)约等于20次磁盘IO时间20*100.2s log2(N) 相当于2的多少次方立方等于N例log2 (8 32的20次方1048576所以就是20次磁盘IO 不支持范围查询快速查找范围查询时需要从根节点多次遍历查询效率比较低
2.二叉树的演进之多叉树 背景 平衡二叉树操作效率高但是存在不少问题常规需要把树加载到内存里面 如果节点少则没问题但是如果节点多 则高度很大进行IO操作则存在性能问题 场景 平衡二叉树每个节点只存储一个键值和数据的每个磁盘块仅仅存储一个键值和数据如果要存储海量的数据那构建平衡二叉树的时候耗时多如果平衡二叉树的节点将会非常多高度也会极其高查找数据时会进行很多次磁盘 IO效率将会极低 为了解决平衡二叉树的这个问题设计一种单个节点可以存储多个键值和数据的平衡树也就是我们接下来要说的 多叉树 多叉树 也叫 多路查找树muitl-way search tree 每一个节点的子树可以多于两个且每一个节点处可以存储多个元素常见的就是B树、B树等 注意B是Balanced意思不是Binary的意思 多叉树通过重新组织节点降低了树的高度可以提高IO效率 应用 操作系统IO操作都会利用磁盘预读原理如果一个节点大小是一个存储页4KB 存储每个节点只需要一次IO即可完成存储 B树在存储系统里面广泛应用比如数据库系统、文件系统等 都会利用磁盘预读原理如果一个节点大小是一个存储页4KB 存储每个节点只需要一次IO即可完成存储 B树在存储系统里面广泛应用比如数据库系统、文件系统等 具体多叉树的应用及原理B-Tree和BTree的底层逻辑会在 MySQL底层存储B-Tree和BTree原理分析 中解释说明
