树与存储

本文涉及的产品
注册配置 MSE Nacos/ZooKeeper,182元/月
Serverless 应用引擎免费试用套餐包,4320000 CU,有效期3个月
任务调度 XXL-JOB 版免费试用,400 元额度,开发版规格
简介: 二叉树: 一个根节点,每个节点下挂着最多2个子节点。、 概念: 度:结点的分支数,二叉树度为2。 深度:树的层次。 二叉排序树: 二叉树的基础上,每个节点上都有一个数字,节点上的数字都比右节点上的大。 应用场景: 基于内存的排序数据结构,写入时将数据写入到对应的位置。数据可能会出现倾
二叉树:

一个根节点,每个节点下挂着最多2个子节点。、

概念:

度:结点的分支数,二叉树度为2。

深度:树的层次。

二叉排序树:

二叉树的基础上,每个节点上都有一个数字,节点上的数字都比右节点上的大。

应用场景:

基于内存的排序数据结构,写入时将数据写入到对应的位置。数据可能会出现倾斜,可以想到数字写入顺序如果不是50-20-60-18-55,而是18-20-50-55-60,那么二叉树就会退变为链表。



B-树:

B-树每个节点上包含着数据和指针,每个指针指向其一个子节点的位置,并且数据的个数为指针的2d-1个。这里的d是指针的个数,同时也是树的“度”。

B-树的查找需要一次对每个节点进行二分查找,直至找到或返回null。通常,可以引入布朗过滤器等方式加速查找。


B-树的写入、删除时要进行分裂、合并、转移等操作,越是非顺序的插入就越容易碰到这些高性能消耗的操作。

应用场景:

一般B-树常常作为磁盘的查找的数据结构使用。

一般磁盘为了减少寻道时间,往往会进行预读,一次读入1个或多个page的数据。我们只要将B-树的每个节点控制在一个page大小,就可以保证,磁盘一次的查找只需要一次IO。一个page大小一般在4k,可以存储不少的数据,假设一个节点存储数据量为100,深度为3的B-树,即可保存100w数据量(100*100*100),而100的数据一般用不了4k的存储空间。

当然,这里节点中存储的东西主要包括data和指针,指针大小是固定的,而数据有大有小。只要控制好每个数据块的大小,就可以提高B-树的性能。

另外,一般情况下非叶子节点占用空间一般较小,上面的例子中,非叶子节点数据量只有1w,完全可以缓存至内存中,这点也是在实际数据库实现中常常使用到的优化。

B+树:

B+树完全是对B-树的工程级优化,非叶子节点不在存储data,只有根节点才存储数据。最大程度的加大了单个page中指针的个数,增加数的度。减少了树的层次。

另外相比较于B-树,其key的个数变为指针个数的2d个。

应用场景:

实际在数据库系统中使用时,往往每个叶子节点都会存储一个其相邻节点的一个指针,用来在范围查找时有更好的性能。

相关文章
|
分布式计算 安全 大数据
maxcomputer的介绍
maxcomputer的介绍
1345 3
|
SQL 存储 资源调度
实时计算 Flink版产品使用问题之如何对starrocks进行分桶
实时计算Flink版作为一种强大的流处理和批处理统一的计算框架,广泛应用于各种需要实时数据处理和分析的场景。实时计算Flink版通常结合SQL接口、DataStream API、以及与上下游数据源和存储系统的丰富连接器,提供了一套全面的解决方案,以应对各种实时计算需求。其低延迟、高吞吐、容错性强的特点,使其成为众多企业和组织实时数据处理首选的技术平台。以下是实时计算Flink版的一些典型使用合集。
|
12月前
|
文字识别 自然语言处理 数据可视化
Qwen2.5 全链路模型体验、下载、推理、微调、部署实战!
在 Qwen2 发布后的过去三个月里,许多开发者基于 Qwen2 语言模型构建了新的模型,并提供了宝贵的反馈。在这段时间里,通义千问团队专注于创建更智能、更博学的语言模型。今天,Qwen 家族的最新成员:Qwen2.5系列正式开源
Qwen2.5 全链路模型体验、下载、推理、微调、部署实战!
|
存储 运维 监控
干货:P2P直连访问---家用摄像头安全使用姿势
随着家用安防摄像头使用的增多,有关安全隐私的问题层出不穷。本文以TP-LINK摄像头为例,旨在探索如何远程直连方式安全使用安防设备
2324 1
干货:P2P直连访问---家用摄像头安全使用姿势
|
Cloud Native Java Linux
安装Nacos
可以理解 Nacos 就是 Euraka + springCloud Config 的集合。也就是服务注册和配置管理
1319 0
|
关系型数据库 5G 调度
PHY 层 | 带你读《5G 空口设计与实践进阶 》之十三
PHY 层也即物理层,位于空口协议栈的最底层,主要负责编码、物理层HARQ 处理、调制、多天线处理以及信号在相应时频资源上的映射等。
PHY 层 | 带你读《5G 空口设计与实践进阶 》之十三
|
存储 弹性计算 Linux
Linux指令入门-磁盘管理
本教程介绍Linux系统中常用的磁盘管理命令。
Linux指令入门-磁盘管理
|
弹性计算 Java Linux
ECS心得
ECS心得
583 1