Tim

一枚野生程序员~

  • 主页
  • 分类
  • 标签
  • 归档
  • 关于
所有文章 工具

Tim

一枚野生程序员~

  • 主页
  • 分类
  • 标签
  • 归档
  • 关于

BTree与B+Tree

阅读数:次 2020-02-26
字数统计: 1.4k字   |   阅读时长≈ 4分

其实在之前的文章说说到过MySQL索引,只不过没细说,《JOIN查询与索引简介》 ,现在来看看回顾一下索引相关的数据结构,首先看看索引的定义: 索引(Index)是帮助MySQL高效获取数据的数据结构。 我不会索引就是类似于字典这样的话泛泛而谈,而是如何真正去理解索引。

img

根据列字段信息的特点,去用一种数据结构存储这些特点,这就是索引,如上图:我们需要把第二列的值通过二叉查找树存储起来,每一个节点都是以Key-Vlaue的形式存在,把值当做Key,把物理地址当做Value,那么只要根据二叉查找树的特性,很快就可以找到对应的物理地址,从而取出数据。

数据库常见的索引有Btree、B+tree、Hash索引等等,今天主要探讨的是BTree和B+Tree

B Tree

先看看Btree的定义:

  • 根节点至少包括两个孩子
  • 树中每个节点最多含有m个孩子( m>=2 )
  • 除根节点和叶节点外,其他每个节点至少有ceil(m/2)个孩子,这里的ceil是取上限的意思
  • 所有叶子节点位于同一层

假设每个非终端结点中包含有n个关键字信息,其中

  • Ki (i=1..n)为关键字,且关键字按顺序升序排序K(i-1) < Ki
  • 关键字的个数n必须满足: [ceil(m / 2) -1] <= n <= m-1
  • 非叶子结点的指针: P[1],P[2],… P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1],K[i])的子树

看起来是非常绕的,通过下面的图示其实是蛮好懂的:

mark

由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。

但是由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质,在这里先不讨论插入删除新的数据记录的问题。

B+Tree

B+树是B树的变体, B-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构。 B+树的定义基本与B树相同,除了:

  • 非叶子节点的子树指针与关键字个数相同
  • 非叶子节点的子树指针P[i],指向关键字值[K[i],K[i+1])的子树
  • 非叶子节点仅用来作为索引,数据都保存在叶子节点中
  • 所有叶子节点均有一个链指针指向下一个叶子结点

mark

B+Tree更适合做索引

1、B+Tree的磁盘读写代价更低

B+Tree内部并没有指向关键字具体信息的指针,也就是不存放数据,只存放索引信息,所能容纳的关键字数量也就越多,一次性读入内存需要查找的关键字也就越多,相对来说IO读写次数也就降低了

2、B+Tree的查询效率更加稳定

由于B+Tree内部节点并不是直接指向文件内容的节点,而只是叶子节点中关键字的索引,所以任何关键字的查找必须走一条从根节点到叶子节点的路,所有关键字查询的路径长度相同,导致每一个数据的查询效率也几乎是相同的,所以查询效率更稳定

3、B+Tree更有利于对数据库的扫描

B Tree在提高了磁盘IO性能的同时,并没有解决元素遍历的效率底下的问题,而B+Tree只需要遍历叶子节点就可以解决对全部关键字信息的扫描,所以对于数据库频繁使用的范围查询是非常有利的

这也就是选择B+Tree作为主流索引数据结构的原因

Hash索引

有些数据库存储引擎还支持Hash这个数据结构作为其索引哈希结构,想必大家已经非常熟悉了,就是根据哈希函数的运算,那只需经过一次定位便能找到需要的数据,相比起B+Tree索引,需要从根节点到非叶子节点,再到叶子节点才能访问到我们需要的数据,这样可能会经过多次的IO访问,所以呢,哈希索引的查询效率理论上要高于B+Tree索引。

mark

但是Hash也是有非常明显的缺点的:

1、仅仅能满足“=” 、“IN”,不能使用范围查询

2、无法被用来避免数据的排序操作

3、不能利用部分索引建来查询

4、不能避免表扫描

5、遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高

赏

谢谢你请我喝咖啡

支付宝
微信
  • 本文作者: Tim
  • 本文链接: https://zouchanglin.cn/508226191.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 许可协议。转载请注明出处!
  • 索引
  • MySQL
  • 数据库

扫一扫,分享到微信

密集索引和稀疏索引
HTTPS协议实现原理
  1. 1. B Tree
  2. 2. B+Tree
  3. 3. B+Tree更适合做索引
  4. 4. Hash索引
© 2017-2021 Tim
本站总访问量次 | 本站访客数人
  • 所有文章
  • 工具

tag:

  • 生活
  • Android
  • 索引
  • MySQL
  • 组件通信
  • Nginx
  • JavaSE
  • JUC
  • JavaWeb
  • 模板引擎
  • 前端
  • Linux
  • 计算机网络
  • Docker
  • C/C++
  • JVM
  • 上传下载
  • JavaEE
  • SpringCloud
  • Golang
  • Gradle
  • 网络安全
  • 非对称加密
  • IDEA
  • SpringBoot
  • Jenkins
  • 字符串
  • vim
  • 存储
  • 文件下载
  • Mac
  • Windows
  • NIO
  • RPC
  • 集群
  • 微服务
  • SSH
  • 配置中心
  • XML
  • Chrome
  • 压力测试
  • Git
  • 博客
  • 概率论
  • 排序算法
  • 分布式
  • 异常处理
  • 文件系统
  • 哈希
  • openCV
  • 栈
  • 回溯
  • SpringCore
  • 流媒体
  • rtmp
  • 面向对象
  • Vue
  • ElementUI
  • 软件工程
  • 异步
  • 自定义UI
  • ORM框架
  • 模块化
  • 交互式
  • Jsoup
  • Http Client
  • LRUCache
  • RabbitMQ
  • 消息通信
  • 服务解耦
  • 负载均衡
  • 权限
  • 多线程
  • 单例模式
  • Protobuf
  • 序列化
  • Python
  • m3u8
  • 堆
  • 二叉树
  • 自定义View
  • 观察者模式
  • 设计模式
  • 线程池
  • 动态扩容
  • 高可用
  • GC
  • ffmpeg
  • SpringMVC
  • REST
  • Redis
  • 缓存中间件
  • UML
  • Maven
  • Netty
  • 高性能网络
  • IPC通信
  • IO
  • Stream
  • 发布订阅
  • SQLite
  • Hash
  • 集合框架
  • 链表
  • Lambda
  • 汇编语言
  • 组件化
  • Router
  • 开发工具

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia-plus根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 思维导图
  • PDF工具
  • 无损放大
  • 代码转图
  • HTTPS证书