icode icode
首页
  • Android学习

    • 📁基础内容
    • 📺AndroidCore
    • 🎨Android-UI
    • 🏖️Components
    • 📊Fragment
    • 🔗网络操作
    • 🔏异步机制
    • 📦数据存储
    • 🗃️Gradle
  • 学习笔记

    • 『框架』笔记
    • 『Kotlin』笔记
    • 《Vue》笔记
    • 《Git》学习笔记
    • 『Bug踩坑记录』
  • ListView
  • RecyclerView
  • ViewPager
  • Java笔记

    • 🟠JavaSE
    • 🟢JavaWeb
    • 🔴JavaEE
    • ⚪JavaTopic
    • 🍳设计模式
  • 计算机基础

    • 📌计算机网络
    • 🔍数据结构
    • 📦数据库
    • 💻OS
  • 技术文档
  • GitHub技巧
  • Nodejs
  • 博客搭建
  • 学习
  • 面试
  • 心情杂货
  • 实用技巧
  • 友情链接
  • 关于

    • 📫关于我
  • 收藏

    • 网站
    • 资源
    • Vue资源
  • 分类
  • 标签
  • 归档
GitHub (opens new window)

iqqcode

保持对技术的探索实践与热爱
首页
  • Android学习

    • 📁基础内容
    • 📺AndroidCore
    • 🎨Android-UI
    • 🏖️Components
    • 📊Fragment
    • 🔗网络操作
    • 🔏异步机制
    • 📦数据存储
    • 🗃️Gradle
  • 学习笔记

    • 『框架』笔记
    • 『Kotlin』笔记
    • 《Vue》笔记
    • 《Git》学习笔记
    • 『Bug踩坑记录』
  • ListView
  • RecyclerView
  • ViewPager
  • Java笔记

    • 🟠JavaSE
    • 🟢JavaWeb
    • 🔴JavaEE
    • ⚪JavaTopic
    • 🍳设计模式
  • 计算机基础

    • 📌计算机网络
    • 🔍数据结构
    • 📦数据库
    • 💻OS
  • 技术文档
  • GitHub技巧
  • Nodejs
  • 博客搭建
  • 学习
  • 面试
  • 心情杂货
  • 实用技巧
  • 友情链接
  • 关于

    • 📫关于我
  • 收藏

    • 网站
    • 资源
    • Vue资源
  • 分类
  • 标签
  • 归档
GitHub (opens new window)
  • 排序算法

  • 线性表

  • 树

    • B+树
      • 1. 红黑树与B树的区别
      • 2. B树
        • B树的优点
      • 3. B+树
        • 3.1 B+树存储数据
        • 3.2 B+ 树的优点
      • 4. B+树在数据库中的应用
        • 4.1 未建立主键索引查询
        • 4.2 建立主键索引查询
    • 红黑树
    • 二叉树-层序遍历
  • 数据结构
  • 树
iqqcode
2021-06-17
目录

B+树

# 1. 红黑树与B树的区别

  1. B树又叫平衡多路查找树。B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。与红黑树很相似,但在降低磁盘I/0操作方面要更好一些。
  2. 红黑树与B树的区别在于,B树的结点可以有许多子女,从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样,一棵含n个结点的 B树的高度也为O(lgn) ,但可能比一棵红黑树的高度小许多,应为它的分支因子比较大。所以, B树可以在O(logn)时间内,实现各种如插入(insert),删除(delete)等动态集合操作

# 2. B树

B树中允许一个结点中包含多个key,可以是3个、4个、5个甚至更多,并不确定,需要看具体的实现。现在我们选择一个参数M,来构造一个B树,我们可以把它称作是M阶的B树,那么该树会具有如下特点:

  • 每个结点最多有M-1个key,并且以升序排列;

  • 每个结点最多能有M个子结点;

  • 根结点至少有两个子结点;

image-20200823070706890

# B树的优点

由于B树的每一个节点都包含key和value,因此我们根据key查找value时,只需要找到key所在的位置,就能找到value,但B+树只有叶子结点存储数据,索引每一次查找,都必须一次一次,一直找到树的最大深度处,也就是叶子结点的深度,才能找到value。

# 3. B+树

B+树是对B树的一种变形树,它与B树的差异在于:

  1. 非叶结点仅具有–索引作用,也就是说,非叶子结点只存储key,不存储value;
  2. 树的所有叶结点构成一个有序链表,可以按照key排序的次序遍历全部数据。

# 3.1 B+树存储数据

若参数M选择为5,那么每个结点最多包含4个键值对,我们以5阶B+树为例,看看B+树的数据存储。

image-20200816154755778

# 3.2 B+ 树的优点

  1. 由于B+树在非叶子结点上不包含真正的数据,只当做索引使用,因此在内存相同的情况下,能够存放更多的key

  2. B+树的叶子结点都是相连的,因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历


# 4. B+树在数据库中的应用

在操作数据库时,我们为了提高查询效率,可以基于某张表的某个字段建立索引,就可以提高查询效率,那其实这个索引就是B+树这种数据结构实现的。

# 4.1 未建立主键索引查询

image-20200816154924284

执行select * from user where id=18,需要从第一条数据开始,一直查询到第6条,发现id=18,此时才能查询出目标结果,共需要比较6次;

# 4.2 建立主键索引查询

image-20200816154959264

执行select * from user where id = 18 ,如果有了索引,由于B+树的叶子结点形成了一个有序链表,所以我们只需要找到id为12的叶子结点:

  • 18 > 12,在12节点的右孩子
  • 遍历右孩子链表,根据key=18,找到其地址即可

按照遍历链表的方式顺序往后查即可,共查询了3次,效率非常高。

在区间查询时,效率体现的更加明显

编辑 (opens new window)
上次更新: 2021/06/27, 10:49:09
顺序表
红黑树

← 顺序表 红黑树→

最近更新
01
匿名内部类
10-08
02
函数式接口
10-08
03
ARouter-Kotlin踩坑
10-05
更多文章>
Theme by Vdoing | Copyright © 2021-2023 iqqcode | MIT License | 备案号-京ICP备2021028793号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式
×