昆山市住房和城乡建设局网站,网站关键词找不到,自适应网站主要用什么做,人社通成都app下载项目场景#xff1a;
图灵奖获得者#xff08;Niklaus Wirth #xff09;说过#xff1a; 程序 数据结构 算法#xff0c; 也就说我们无时无刻 都在和数据结构打交道。 只是作为 Java 开发#xff0c;由于技术体系的成熟度较高#xff0c;使得大部分人认为#xff1…项目场景
图灵奖获得者Niklaus Wirth 说过 程序 数据结构 算法 也就说我们无时无刻 都在和数据结构打交道。 只是作为 Java 开发由于技术体系的成熟度较高使得大部分人认为程序应该等于 框 架 SQL 问题分析与描述 从二方面方面来思考 了解二叉树、AVL 树、B 树的概念B 树和 B树的应用 B 树是一种多路平衡查找树为了更形象的理解如下图所示。 二叉树每个节点支持两个分支的树结构相比于单向链表多了一个分支。 二叉查找树在二叉树的基础上增加了一个规则左子树的所有节点的值都小于它的根 节点右子树的所有子节点都大于它的根节点。如下图所示。 二叉查找树会出现斜树问题导致时间复杂度增加因此又引入了一种平衡二叉树它具有二叉查找树的所有特点同时增加了一个规则”它的左右两个子树的高度差的绝对值不超过 1“。平衡二叉树会采用左旋、右旋的方式来实现平衡。如下图所示。 而 B 树是一种多路平衡查找树它满足平衡二叉树的规则但是它可以有多个子树子树的数量取决于关键字的数量比如这个图中根节点有两个关键字 3 和 5 那么它能够拥有的子路数量关键字数1。 如下图所示。 因此从这个特征来看在存储同样数据量的情况下平衡二叉树的高度要大于 B 树 B树其实是在 B 树的基础上做的增强最大的区别有两个 a. B 树的数据存储在每个节点上而 B树中的数据是存储在叶子节点并且通过链表的方 式把叶子节点中的数据进行连接。 b. B树的子路数量等于关键字数
---------------------------------------------------------------------------------------------------------------------------------
如下图所示这个是 B 树的存储结构从 B 树上可以看到每个节点会存储数据。 如下图所示这个是 B树B树的所有数据是存储在叶子节点并且叶子节点的数据是用双向链表关联的。 2. B 树和 B树一般都是应用在文件系统和数据库系统中用来减少磁盘 IO 带来的性能损耗。 以 Mysql 中的 InnoDB 为例当我们通过 select 语句去查询一条数据时InnoDB 需要从磁盘上去读取数据这个过程会涉及到磁盘 IO 以及磁盘的随机 IO如图所示 我们知道磁盘 IO 的性能是特别低的特别是随机磁盘 IO。 因为磁盘 IO 的工作原理是首先系统会把数据逻辑地址传给磁盘磁盘控制电路按照寻址逻辑把逻辑地址翻译成物理地址也就是确定要读取的数据在哪个磁道哪个扇区。 为了读取这个扇区的数据需要把磁头放在这个扇区的上面为了实现这一个点磁盘 会不断旋转把目标扇区旋转到磁头下面使得磁头找到对应的磁道这里涉及到寻道事件以及旋转时间。 很明显磁盘 IO 这个过程的性能开销是非常大的特别是查询的数据量比较多的情况下。 所以在 InnoDB 中干脆对存储在磁盘块上的数据建立一个索引然后把索引数据以及 索引列对应的磁盘地址以 B树的方式来存储。 如图所示当我们需要查询目标数据的时候根据索引从 B树中查找目标数据即可 由于 B树分路较多所以只需要较少次数的磁盘 IO 就能查找到。 3. 为什么用 B 树或者 B树来做索引结构原因是 AVL 树的高度要比 B 树的高度要高而高度就意味着磁盘 IO 的数量。所以为了减少磁盘 IO 的次数文件系统或者数据库才会采用 B 树或者 B树。 结尾 数据结构在实际开发中非常常见比如数组、链表、双向链表、红黑树、跳跃表、B 树、 B树、队列等。 数据结构是编程中最重要的基本功之一。 学了顺序表和链表我们就能知道查询操作比较多的场景中应该用顺序表修改操作比 较多的场景应该使用链表。 学了队列之后就知道对于 FIFO 的场景中应该使用队列。 学了树的结构后会发现原来查找类的场景还可以更进一步提升查询性能。 基本功决定大家在技术这个岗位上能够走到的高度。
