云南省文山州网站建设,怎么在网上卖东西?,WordPress搭载个人博客,做展厅 参考什么网站首先#xff0c;我们来想想为什么这么多数据结构#xff0c;为什么要用树这种数据结构#xff1f;
众多的数据结构在逻辑层面可分为#xff1a;线性结构 和 非线性结构。
线性结构有#xff1a;数组、链表#xff0c;基于它们衍生出的有哈希表#xff08;哈希表也称散…首先我们来想想为什么这么多数据结构为什么要用树这种数据结构
众多的数据结构在逻辑层面可分为线性结构 和 非线性结构。
线性结构有数组、链表基于它们衍生出的有哈希表哈希表也称散列表、栈、队列等。
非线性结构有树、图。
还有其他数据结构如跳表、位图 也都由基础数据结构演化而来不同的数据结构存在即都是为了解决某些场景问题。
如果要知道索引适合什么数据结构那我们得先来回答索引需要来解决什么样的问题痛点和发挥着什么样的作用其次再才是选择什么样的数据结构后者只是果前者才是因。
我们都知道MySQL存储的数据是在磁盘里因为即使设备断电放在磁盘的数据是不会有影响的保障了数据不丢失这意味着MySQL在磁盘上的数据是持久化的。
但数据存储在磁盘得到保障的同时也是有代价的这代价就是磁盘的处理速度是毫秒级别的相比内存纳秒级别的速度简直是小巫见大巫。
这里简单介绍一下跳图的概念
跳表底层实质就是可以进行二分查找的有序链表。而且在链表基础加上索引层。即能支持插入、删除等动态操作也支持按区间高效查询。而且不管是查找、插入、删除对应的时间复杂度都是 O(logn)。
要理解跳表先来看链表假设链表存储是有序的数据我们要想查询某一个数据在最差的情况下要从头全遍历整个链表时间复杂度是 O(n)。 从上图所示我们如果要查询一个 26 的节点跳表就可以先从索引层遍历当遍历到在索引层的 21 节点会发现下一个索引层的节点是 36 节点时很明显要找的 26 的节点就在这区间。此时我们只要再通过索引层指向原始链表的指针往下移到原始链这一层遍历只要遍历 2 个节点即可找到 26 了。如果用原来的链表需要遍历 10 个节点现在只要遍历 8 个节点。 如下图中一图胜千言。当数据量大时一个包含多个结点的链表在建立了五级索引后可以突显的看到索引层的优势。同时注意道这样一个规律 “加一层索引查询所需要遍历的节点个数减少查询效率也就提高了。” 从用户的角度就是跳表这家伙其实就是在告诉链表从什么地方开始找比较快 那为什么不用跳表作为MySQL的底层索引结构呢
可以从尽量减少从磁盘查询这个角度寻找答案这里就不做过多描述了~
接下来看树这么多树为什么要选择B树
直接跳到AVL(平衡二叉树)树来讲讲AVL树可以保证每一个节点他的左右子树的高度差都不会超过1这样相较于二叉查找树来讲可以有效防止链化但是随着数据变多这棵树整个高度也会变高同样会提高磁盘的查询效率~
为了解决这样的问题我们后面又引入了B树(B-树)因为B树这种数据结构他的一个节点就可以存在多个子节点同时一个节点里面又可以存储多个元素这样就有效解决了前面AVL树带来的问题 那我们来看一下上图所示当一颗3阶的B树查找 90 这个的元素时的流程是怎么样的
先从根节点出发也就是 磁盘块1判断 90 在17 ~ 35之间通过磁盘块1中的指针 p3 找到磁盘块4。还是按照原来的步骤在磁盘块4中的65 ~ 87之间相比较最后磁盘4的指针p3找到磁盘块11。也就找到有匹配90的键值。
可以发现一颗3阶的B树在查找叶子节点时由于树高度只有 3所以查找过程最多只需要3次的磁盘I/O操作。
数据量不大时可能不太真切。但当数据量大时节点也会随着增多此时如果还是前面的自平衡二叉树的场景下由于二叉树只能最多2个叶子节点的约束也只能纵向去的去扩展子节点树的高度会很高意味着需要更多的操作磁盘I/O次数。而B树则可以通过横向扩展节点从而降低树的高度所以效率自然要比二叉树效率更高。直白说就是变矮胖了
看到这相信你也知道如果B树这么适合也就没有接下来B树的什么事了。
接着那为什么不用B树而用了B树呢
你看啊B树其实已经满足了我们最前面所要满足的条件减少磁盘I/O操作同时支持按区间查找。但注意虽然B树支持按区间查找但并不高效。例如上面的例子中B树能高效的通过等值查询 90 这个值但不方便查询出一个区间内3 ~ 10区间内所有数的结果。因为当B树做范围查询时需要使用中序遍历那么父节点和子节点也就需要不断的来回切换涉及了多个节点会给磁盘I/O带来很多负担。
好那最后我们再来看看为什么要用B树
B树这种结构他的每一个节点存放的都是索引所有值都是存放在叶子结点里面的而叶子节点之间构成一个从小到大有序的链表互相指向相邻的叶子节点也就是叶子节点之间形成了有序的双向链表。 所以相对于B树而言B树在删除节点过程中会添加复杂的删除节点的操作没有冗余节点但是对于B树来说只会在叶子结点上进行操作非叶子节点不做处理有冗余节点但是不会涉及到复杂的树变形而且对于插入来讲B树的插入最多也只需要修改一条路径也不涉及复杂度算法实现可以类似于红黑树的旋转去实现平衡。
