专栏首页JetpropelledSnakeSQL学习笔记之B+树

SQL学习笔记之B+树

0x00 概述

要描述清楚B+树,得先了解二叉查找数,平衡二叉树。

0x01 二叉查找树

任意节点,它的左子树如果不为空,那么左子树上所有节点的值都小于根节点的值; 任意节点,他的右子树如果不为空,那么右子树上的所有节点的值大于根节点的值。

这个特性给查找带来了方便,如上图,要找key=3的键值,只要从6这个节点左子树进行递归查找即可,右子树的节点可以完全不理会。

0x02 平衡二叉树

二叉查找树有些缺陷,因为它对树的左右子树的高度没有任何限制,极端的情况下会出现如下图的类似链表的情况:

这种二叉查找树对查询没任何好处的。所以有必要将树节点的左右子树的高度做一下限制,尽量保持平衡。

 二叉平衡树 图一

二叉查找树 图二

二叉平衡树要求节点的左右子树的高度不要相差超过1,像图二中的6这个节点,它的左子树的高度是4,右子树的高度是2,相差超过了1,不具备平衡二叉树的特性。

由二叉平衡树的特性可以看到,查询的效率同样很高,同时又避免了二叉查找树出现链表那种极端情况。

 0x03 B+树

B+树有几个特点: 1、是多叉而不是二叉了,使用多叉的目的是降低树的高度; 2、每个节点不再只是存储一个key了,可以存储多个key; 3、非叶子节点存储key,叶子节点存储key和数据。 4、叶子节点两两相连,为顺序查询提供了帮助

0x04 Mysql为什么选择B+树

1、B+树的非叶子节点只是存储key,占用空间非常小,因此每一层的节点能索引到的数据范围更加的广。换句话说,每次IO操作可以观看更多的数据;

2、叶子节点两两相连,符合磁盘的预读特性。如图三中存储50和55的叶子节点,它有个指针指向了60和62这个叶子节点,那么当我们从磁盘读取50和55对应的数据的时候,由于磁盘的预读特性,会顺便把60和62对应的数据读取出来。这个时候属于顺序读取,而不是磁盘寻道了,加快了速度。

3、支持范围查询,而且部分范围查询非常高效,原因是数据都是存储在叶子节点这一层,并且有指针指向其他叶子节点,这样范围查询只需要遍历叶子节点这一层,无需整棵树遍历。

0x05 Mysql 索引简单描述

innodb存储引擎

自增主键索引

自增主键索引就是使用了B+树,索引文件同时也是数据文件,存储了整张表的数据。也就是说,平时我们执行sql按照主键查询的时候,那么只需要从这个索引文件获取数据即可。这种索引也叫聚集索引 ,原因是所有数据是按照主键聚集的。

辅助索引(非自增主键索引,也可以叫非聚集索引)

这种索引文件的叶子节点存储了键值和书签。键值说的就是列的值,书签就是对应记录的主键的值,如果按照某个辅助索引来查询数据的时候,如果没有用到覆盖索引,那么就得分两步走: 1、先从辅助索引文件中获取到数据对应的主键; 2、根据主键从聚集索引中获取真实数据。

MyISAM存储引擎

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。这种称为非聚集索引,这个命名其实是对应上面innodb的叫法而已。

 参考

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SQL学习笔记之MySQL索引知识点

    之前写过一篇Mysql B+树学习,简单的介绍了B+数以及MySql使用B+树的原因, 有了这些基础知识点,对MySql索引的类型以及索引使用的一些技巧,就...

    Jetpropelledsnake21
  • SQL学习笔记五之MySQL索引原理与慢查询优化

    一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,在生产环境中,我们遇到最多的,也是最容易出问题的,还是一些复杂的查询操作,...

    Jetpropelledsnake21
  • SQL学习笔记之B+树的几点总结

    本文主要以列表形式将B+树的特点以及注意点等列出来,主要参考《算法导论》、维基百科、各大博客的内容,结合自己的理解写的,如内容有不当之处,请各位雅正。

    Jetpropelledsnake21
  • BAT大厂都会问的MySQL底层数据结构

    左边子节点的数据小于父节点数据,右边子节点的数据大于父节点数据。如果col2是索引,查找索引为89的行元素,那么只需要查找两次,就可以获取到行元素所在的磁盘指针...

    程序员小强
  • 数据库索引

    数据库索引,在日常工作中会经常接触到,比如某一个 SQL 查询比较慢,分析原因后,经常会说 “给某个字段加个索引”,索引又是如何工作的?

    王小明_HIT
  • 一文带你深入理解Mysql索引底层数据结构与算法

    首先看一下,在数据库没有加索引的情况下,SQL中的where语句是如何查找目标记录的,首先看到下图的Col2字段,如果我们要查找where col2 = 89的...

    黎明大大
  • MySQL|索引背后

    01 索引 以MySQL中的索引为例子总结。 数据库查询是数据库的最主要功能之一,实现高效的查询速度一定是MySQL非常关心的事情。 索引(Index)正是帮...

    double
  • 面试题-Mysql索引原理

    大家是不是感觉弱爆了,随着工作经验的增加,我对索引有了更深入的了解,下面就来分享下我眼中的索引,分享以问题的形式,从敲门到进门。

    别明天就今天吧
  • 5人法则:小样本也有力量

    假如,你想知道你们公司每个员工的通勤时间是多少。而公司员工有上千人,一个一个问太费时。你并不需要得到精确的结果,有没有好的办法呢?

    Stanley Sun
  • Elasticsearch UNASSIGNED索引分片问题分析

    线上突然有一台服务器宕机重启了,从而导致Elastisearch集群有些索引的分片出现UNASSIGNED的状态,情况如下:

    后场技术

扫码关注云+社区

领取腾讯云代金券