树的结构(b,b+树)

无论线性表,栈还是队列,都是一对一,查询的时候,效率较低,数据量比较的大的情况

1.树的定义

一种数据结构,有层次关系的集合,根朝上,叶朝下

除了根节点外,每个子节点都有多个不想交的子树

父节点

子节点

兄弟节点

树根节点(根节点)

叶子节点

子树

空树

度:最大子树数,多少分支

层次(深度):第一层,第二次,以此类推,最大层数是4

森林:树多了

2.二叉树

树中包含的各个节点不能超过2,度不能超过2

二叉树衍生出满二叉树和完全二叉树,二叉树分为顺序存储的二叉树,基于链表存储的二叉树。

二叉排序树,平衡二叉树,赫夫曼树,红黑树,都是属于二叉树。

2.1二叉排序树,搜索树

比它小放它左边,比它大放右边。

查找复杂度较低,o(logn)

插入的数据总是比已有的数据大,子树会向一边切斜,树的层次变深,形成链表结构,出现了平衡二叉树。

2.2平衡二叉树

子树的高度不大于1,查询速度快,插入和删除慢,要进行旋转和平衡度计算。为了解决删除插入比较耗时,出现了红黑树

2.3红黑树

在平衡二叉树上增加了红色或黑色,增加了颜色属性

根节点和叶子节点是黑色,内部节点是红色和黑色较低,叶子节点必须是黑色,根节点只能是黑色。

从根节点走到空节点,所经过的黑节点的数目是相同的。

左旋和右旋,翻转颜色

AVL树和rb树的区别

3.多叉树

大规模数据存储,二叉树树的深度过深,导致查询效率低下,磁盘io读写过于频繁,导致查询效率低下,多叉树能够解决这个问题

b树,b+树

3.1 b-tree

b树适用于读写相对大的数据块的存储系统

每个节点可以存储超过2个元素,可以超过2的字节点

拥有AVL平衡树的特点

拥有二叉搜索树的特点

B树比较矮,分叉越多,树越矮,io次数较少,搜索性能较高。

三阶B树最多有3个分叉,四阶B树最多拥有4个分叉

一个节点最好凑够一个数据块的大小,凑够一个数据块的大小,直接写入磁盘。

一般4096b一个节点,因为一个磁道就4096b,但是不一定,根据你磁盘来弄。

3.2 b+tree

分为非叶子节点,叶子结点

内部节点只存储key,不存储值

叶子节点存储key和value具体数据,、

所有的叶子节点形成一个有序链表,排序和查询范围支持好。

b树的节点存储的元素个数是m,那么它的字节点数是m+1

b+比b树的优势,也是为什么mysql要选择b+树

b+存储更多的key,树的高度更低,时间复杂度越小,查询块

数据在叶子节点,每次都要到叶子节点,查询稳定,都是去第三层。

叶子节点构成链表结构,方便查询和排序

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/377207.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【自动驾驶汽车通讯协议】UART通信详解:理解串行数据传输的基石

文章目录 0. 前言1. 同步通讯与异步通讯1.1 同步通信1.2 异步通信 2. UART的数据格式3. 工作原理3.1 波特率和比特率3.2 UART的关键特性 4. UART在自动驾驶汽车中的典型应用4.1 UART特性4.2应用示例 5. 结语 0. 前言 按照国际惯例,首先声明:本文只是我自…

【周末闲谈】Stable Diffusion会魔法的绘画师

个人主页:【😊个人主页】 系列专栏:【❤️Python】 文章目录 前言Stable Diffusion介绍 使用ComfyUI 和 WebUIComfyUIWebUI 配置需求 Stable Diffusion资源分享吐司AiAUTOMATIC1111Civitai绘世整合包Nenly同学stability.ai 前言 在很早之前&…

香橙派AIpro部署YOLOv5:探索强悍开发板的高效目标检测能力

香橙派AIpro部署YOLOv5:探索强悍开发板的高效目标检测能力 一、香橙派AIpro开箱使用体验 1.1香橙派AIpro开箱 拿到板子后第一件事情就是开箱: 开箱后可以看见一个橘子的标识,也就是香橙派了,并且还有四个大字:为AI…

取消文字默认选中效果

点击的时候会选中文字 .user-select-none {user-select: none;}<div class"model user-select-none" onclick"createRipple(event)">Click me for ripple effect outside </div>点击再快也不会选中了

【C++】——类和对象(上)

文章目录 什么是类和对象类的定义类的访问限定符及其封装类的作用域类的实例化类的对象的大小计算this指针 什么是类和对象 类是一个用户定义的类型&#xff0c;它封装了数据&#xff08;称为属性或成员变量&#xff09;和操作这些数据的方法&#xff08;称为成员函数或方法&a…

Seven layers of the metaverse

看到一篇关于元宇宙的文章&#xff0c;分享给大家&#xff0c;供大家参考。 随着物理世界和数字世界的融合&#xff0c;元宇宙正在推动我们数字能力的新边界。从人类身份、个性和声誉到资产、情感和历史&#xff0c;元宇宙的虚拟现实中可以以全新的方式进行交互、控制和体验。因…

OpenGL笔记十之Shader类的封装

OpenGL笔记十之Shader类的封装 —— 2024-07-10 晚上 bilibili赵新政老师的教程看后笔记 code review! 文章目录 OpenGL笔记十之Shader类的封装1.运行2.目录结构3.main.cpp4.application4.1.CMakeLists.txt4.2.Application.h4.3.Application.cpp 5.assets5.1.shaders&#xf…

【吊打面试官系列-ZooKeeper面试题】简述 Zookeeper 文件系统?

大家好&#xff0c;我是锋哥。今天分享关于 【简述 Zookeeper 文件系统?】面试题&#xff0c;希望对大家有帮助&#xff1b; 简述 Zookeeper 文件系统? Zookeeper 提供一个多层级的节点命名空间&#xff08;节点称为 znode&#xff09;。与文件系统不同的是&#xff0c;这些节…

prometheus+grafana应用监控配置

配置Prometheus 官方地址&#xff1a;Download | Prometheus &#xff08;wegt下载压缩包&#xff0c;解压并重命名prometheus&#xff0c;文件放于/data/prometheus即可&#xff09; 配置 service方法(文件放于 /etc/systemd/system/prometheus.service)&#xff1a; [Unit…

博物馆地图导航系统:高精度地图引擎与AR/VR融合,实现博物馆数字化转型

在人民日益追求精神文化的时代下&#xff0c;博物馆作为传承与展示人类文明的璀璨殿堂&#xff0c;其重要性不言而喻。然而&#xff0c;随着博物馆规模的不断扩大和藏品种类的日益丰富&#xff0c;游客在享受知识盛宴的同时&#xff0c;也面临着“迷路”与“错过”的困扰。博物…

【CUDA】CUDA中缓存机制对计时的影响

笔者在阅读知乎上一个关于CUDA编程的专栏时&#xff0c;发现作者写的很多文章中都会附带计时的模块用于评估程序的运行效率&#xff0c;然而笔者发现&#xff0c;在运行这篇文章中的代码时时&#xff0c;得到的结果和作者的结果有较大差异&#xff0c;主要体现在&#xff1a;使…

前端调试技巧(npm Link,vscode调试,浏览器调试等)

Npm Link 功能&#xff1a; 在本地开发npm模块的时候&#xff0c;我们可以使用npm link命令&#xff0c;将npm 模块链接到对应的运行项目中去&#xff0c;方便地对模块进行调试和测试 断点调试 vscode调试 Debug Vue2 Project 目标&#xff1a;在VSCode中调试项目代码…

巧用 VScode 网页版 IDE 搭建个人笔记知识库!

[ 知识是人生的灯塔&#xff0c;只有不断学习&#xff0c;才能照亮前行的道路 ] 巧用 VScode 网页版 IDE 搭建个人笔记知识库! 描述&#xff1a;最近自己在腾讯云轻量云服务器中部署了一个使用在线 VScode 搭建部署的个人Markdown在线笔记&#xff0c;考虑到在线 VScode 支持终…

[K8S]一、Flink on K8S

Kubernetes | Apache Flink 先编辑好这5个配置文件&#xff0c;然后再直接执行 kubectl create -f ./ kubectl get all kubectl get nodes kubectl get pods kubectl get pod -o wide kubectl get cm -- 获取所有的configmap 配置文件 kubectl logs pod_name -- 查看…

智能汽车域控制器FOTA升级方案探讨

1.概述 本文探讨的OTA升级仅针对运行linux系统的域控制器&#xff0c;升级方式为FOTA&#xff0c;探究升级文件从OTA服务器下载到域控中以后&#xff0c;如何将升级文件安装到存储系统。 为安全起见&#xff0c;支持FOTA升级的存储区域必须支持AB分区设计&#xff0c;每个分区…

浅学三次握手

数据要完成传输&#xff0c;必须要建立连接。由于建立TCP连接的过程需要来回3次&#xff0c;所以&#xff0c;将这个过程形象的叫做三次握手。 结合上面的图来看更清楚。 先说三次握手吧&#xff0c;连接是后续数据传输的基础。就像我们打电话一样&#xff0c;必须保证我和对方…

c++习题10-骑士得到的金币数

目录 一&#xff0c;题目 二&#xff0c;思路 三&#xff0c;代码 一&#xff0c;题目 二&#xff0c;思路 阅读题目之后可以列出如下的数字&#x1f447; 观察上图有如下思路&#xff08;主要是找到规律&#xff09; 给个for循环包裹住需要处理的语句&#xff0c;循环…

k8s快速部署一个网站

1&#xff09;使用Deployment控制器部署镜像&#xff1a; kubectl create deployment web-demo --imagelizhenliang/web-demo:v1 kubectl get deployment,pods[rootk8s-matser ~]# kubectl get pods NAME READY STATUS RESTARTS A…

The Web3 社区 Web3 产品经理课程

概述 / 深耕区块链行业 11 年&#xff0c;和很多产品经理都打过交道&#xff1b;遇到过优秀的产品经理&#xff0c;也遇到过比较拉垮的产品经理。多年工作中&#xff0c;曾在某些团队&#xff0c;承载技术兼产品经理的角色&#xff1b;也参与过很多 Web3 外包项目&#xff0c;包…

【研路导航】成功保研面试:避免迷惑发言,掌握关键表达技巧

更多保研&#xff0c;夏令营&#xff0c;预推免与信息时间节点资讯可以在文章末尾领取&#xff01; 写在前面 在保研面试的过程中&#xff0c;准备充分是成功的关键。每年的夏令营都是竞争激烈的时刻&#xff0c;而如何在面试中展现出最佳的自我&#xff0c;不仅是一场考验&a…