B-tree

B-tree
每个节点维护两个数据,并指向最多 3 个子节点。如图 3 个子节点的数据分别为:小于 17, 17 ~ 35 ,大于 35。

假设,从上图中查找 10 这个数,步骤如下:

  1. 找到根节点,对比 10 与 17 和 35 的大小,发现 10 < 17 在左子节点,也就是第 2 层节点;

  2. 从根节点的指针,找到左子节点,对比 10 与 8 和 12 的大小,发现8 < 10 < 12,数据在当前节点的中间子节点,也就是第 3 层节点;

  3. 通过上步节点的指针,找到中间子节点(第 3 层节点),对比 10 与 9 和 10 的大小,发现 9 < 10 == 10,因此找到当前节点的第二数即为结果。

加上忽略的 12 个数据,从 26 个数据中查找一个数字 10,仅仅用了 log3(26)≈ 3次,而如果用平衡二叉树,则需要log2(26)≈ 5 次,事实证明,多叉树确实可以再次提高查找性能。

多叉树是在二分查找树的基础上,增加单个节点的数据存储数量,同时增加了树的子节点数,一次计算可以把查找范围缩小更多。

优点:二叉平衡树的基础上,使加载一次节点,可以加载更多路径数据,同时把查询范围缩减到更小。

本作品采用《CC 协议》,转载必须注明作者和本文链接
有梦想的人睡不着,没有梦想的人睡不醒。
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
文章
88
粉丝
23
喜欢
134
收藏
269
排名:228
访问:4.2 万
私信
所有博文
博客标签
redis
1
php
1
laravel
7
docker
3
orm
2
sync
1
pivot
1
detach
2
attach
2
算法
1
递归
1
多对多
1
lnmp环境搭建
1
GO变量
1
GO数据类型
1
IOC注入反转
1
IOC容器的绑定解析过程(绑定单例)
1
原生微信网页授权登录(natapp穿墙)
1
VMwareNAT网卡配置
1
MySQL基础架构
1
redis 主从搭建
1
Sentinel哨兵模式解决故障转移
1
elasticsearch安装
1
elasticsearch集群安装3台
1
安装kibana
1
必须了解的mysql三大日志-binlog、redo log和undo log
1
何处理数据恢复 数据丢失 面试tx的架构师的岗位问的
1
分库分表插入数据
1
创建分库分表(在主从复制的基本上)
1
分库分表总结
1
mysql总结
1
haproxy状态检测脚本(完成高可用)
1
mysql高可用衡搭建(Keepalived)
1
mysql负载均衡搭建(haproxy)
1
mysql主从恢复数据一致性(pt工具-t-table-checksum和pt-table-sync)
1
终于解决了《====》记一次mysql热备份xtrabackup(没有解决问题)
1
mysql事务
1
MYSQL8.0安装
1
Redis-cluster分布式集群搭建部署
1
比Redis-cluster还好的redis分布式集群(twemproxy)
1
Redis缓存穿透/缓存雪崩/缓存击穿(案例:产生的原因 解决方案利/弊)
1
数据结构之MySQL独爱B+树(二叉树、AVL树、红黑树、B树对比)
1
B-tree
1
B+tree
1
Mycat实现mysql的负载均衡读写分离
2
mysql双主双从 搭建配置
1
mycat 双主双从-负载均衡-高可用
1
Mycat垂直分库
1
记一次mysql高可用技术分享
1
【rabbitmq】安装ampq的扩展的踩坑总结
1
PHP操作MongoDB(增删改查)
1
golang总结
5
社区赞助商