Mysql 索引 BTree 与 B+Tree 的区别(面试)

目录
  • 前言
  • BTree 基本概念
  • B+Tree 的特点
  • 查找过程的区别
  • B+Tree索引 如何提高索引的查询性能 ？

前言

​ 说起面试，很多同学都经历过，但是 面试中 可能会遇到各种问题，MySQL 的问题 也是非常多，最近我也经常面试，也希望问一些数据库一些偏理论和底层的东西，来考察同学对技术的理解程度， 之后 我会更新这个系列的 面试。

主要更新的内容主要是: 我经常面试 一些面试者 喜欢问的一些问题,这是 第一篇 就更新 数据库相关的吧

BTree 基本概念

B树。B树被称为自平衡树，因为它的节点是按顺序遍历排序的。在B树中，一个节点可以有两个以上的孩子。而且高度在每次更新时都会自动调整。在B树中，数据是按照特定的顺序排序的，最低值在左边，最高值在右边。在B树中插入数据或键，比二叉树更复杂。

Btree 的特点：

  • 节点排序，每个节点 可以存放多个元素，多个元素也是排序的
  • 每个节点 key 和数据在一起
  • B树的所有叶子节点必须在同一级别
  • 在B树的叶子节点上面，不应该有空的子树
  • 在关键字全集内做一次查找，性能逼近 二分查找的算法
  • 任何关键字出现且只出现在一个节点中
  • 搜索有可能在非叶子节点结束，因为数据和索引在一起存储的

来一个 max Degree =3 的一个图

在线生成BTree 的图形

B+Tree 的特点

B+tree 多路平衡查找树：

  • B+Tree 拥有BTree 的所有的结构特点
  • B+Tree 的非叶子节点不存储数据，只存储关键字，叶子节点才存储了所有的数据，并且是排好序的
  • B+Tree 叶子节点是通过指针连接在一起的(双向连接)， 这样在范围查询中发挥作用
  • 相对于 Btree , B+tree 层级更低

B+Trees 特点如下：

图形生成地址

查找过程的区别

两种索引 查找过程的区别：

B+tree 需要找到叶子节点 才能找到数据， 而Btree 可能不需要找到叶子节点 就可以找到数据

B+Tree索引 如何提高索引的查询性能 ？

  • 找得快， 叶子节点双向指针
  • 一次IO 操作，找更多的数据，减少IO 操作，节点不存数据，只存关键字，这样可以存储更多索引的信息，B+tree 层级会降低

为啥 B+Tree 会比 BTree 高度要低呢？

页(Page)是Mysql中磁盘和内存交换的基本单位, 也是Mysql管理存储空间的基本单位。

Page 是InnoDB存储引擎磁盘管理的最小单位，每个页默认16KB，innodb_page_size 可以通过这个参数进行修改

B+Tree 中的非叶子节点 不存储数据， 只存关键字，所以一个Page 中可以容纳更多的索引项， 一是可以降低树的高度，二是 在一个内部节点中可以定位更多的叶子节点。

到此这篇关于Mysql 索引 BTree 与 B+Tree 的区别(面试)的文章就介绍到这了,更多相关Mysql BTree与B+Tre内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • MySQL B-tree与B+tree索引数据结构剖析

    MySQL B-tree与B+tree索引数据结构剖析

    目录 一.产生的背景 1.1 进化要求 二.B-tree 2.1 B-tree特性 三.B+tree 3.1 B+tree特性 四.结论 一.产生的背景 二叉查找树的查找时间复杂度是O(logN),整体的查询效率已经足够高了,那么为什么还会有B树和B+树的进化演进呢? 主要的原因是:二叉树可能会退化成一个线性树,造成磁盘IO次数增高的问题,当有大量的数据存储的时候,二叉查找树查询不能将所有的数据加载到内存中,只能逐一加载磁盘页,每个磁盘对应树的节点,造成大量的磁盘IO操作(最坏的情况IO次数为树

  • MySQL btree索引与hash索引区别

    在MySQL中,大多数索引(如 PRIMARY KEY,UNIQUE,INDEX和FULLTEXT)都是在BTREE中存储,但使用memory引擎可以选择BTREE索引或者HASH索引,两种不同类型的索引各自有其不同的使用范围. B树索引具有范围查找和前缀查找的能力,对于有N节点的B树,检索一条记录的复杂度为O(LogN).相当于二分查找. 哈希索引只能做等于查找,但是无论多大的Hash表,查找复杂度都是O(1). 显然,如果值的差异性大,并且以等值查找(=. <.>.in)为主,Hash索引

  • 获取 MySQL innodb B+tree 的高度的方法

    前言 MySQL 的 innodb 引擎之所以使用 B+tree 来存储索引,就是想尽量减少数据查询时磁盘 IO 次数.树的高度直接影响了查询的性能.一般树的高度在 3~4 层较为适宜.数据库分表的目的也是为了控制树的高度.那么如何获取树的高度呢?下面使用一个示例来说明如何获取树的高度. 示例数据准备 建表语句如下: CREATE TABLE `user` (   `id` int(11) NOT NULL AUTO_INCREMENT,   `name` varchar(100) CHARAC

  • MySQL使用B+Tree当索引的优势有哪些

    MySQL使用B+Tree当索引的优势有哪些

    数据库为什么需要索引呢? 我们都是知道数据库的数据都是存储在磁盘上的,当我们程序启动起来的时候,就相当于一个进程运行在了机器的内存当中.所以当我们程序要查询数据时,必须要从内存出来到磁盘里面去查找数据,然后将数据写回到内存当中.但是磁盘的io效率是远不如内存的,所有查找数据的快慢直接影响程序运行的效率. 而数据库加索引的主要目的就是为了使用一种合适的数据结构,可以使得查询数据的效率变高,减少磁盘io的次数,提升数据查找的速率,而不再是愣头青式的全局遍历. 那索引为啥要用B+Tree的数据结构呢?

  • Mysql中的Btree与Hash索引比较

    mysql最常用的索引结构是btree(O(log(n))),但是总有一些情况下我们为了更好的性能希望能使用别的类型的索引.hash就是其中一种选择,例如我们在通过用户名检索用户id的时候,他们总是一对一的关系,用到的操作符只是=而已,假如使用hash作为索引数据结构的话,时间复杂度可以降到O(1).不幸的是,目前的mysql版本(5.6)中,hash只支持MEMORY和NDB两种引擎,而我们最常用的INNODB和MYISAM都不支持hash类型的索引. 不管怎样,还是要了解一下这两种索引的区别

  • Mysql 索引 BTree 与 B+Tree 的区别(面试)

    目录 前言 BTree 基本概念 B+Tree 的特点 查找过程的区别 B+Tree索引 如何提高索引的查询性能 ? 前言 ​ 说起面试,很多同学都经历过,但是 面试中 可能会遇到各种问题,MySQL 的问题 也是非常多,最近我也经常面试,也希望问一些数据库一些偏理论和底层的东西,来考察同学对技术的理解程度, 之后 我会更新这个系列的 面试. 主要更新的内容主要是: 我经常面试 一些面试者 喜欢问的一些问题,这是 第一篇 就更新 数据库相关的吧 BTree 基本概念 B树.B树被称为自平衡树,因

  • MySQL索引类型Normal、Unique和Full Text的讲解

    MySQL的索引类型有普通索引(normal),唯一索引(unique)和全文索引(full text),合理使用索引可大大提升数据库的查询效率,下面是三种类型的索引的介绍 normal:这是最基本的索引,它没有任何限制,MyIASM中默认的BTREE类型的索引,是我们大多数情况下用到的索引. unique:表示唯一的,不允许重复的索引,如果该字段信息保证不会重复.例如身份证号用作索引时,可设置为unique. full text : 表示全文搜索的索引,仅可用于 MyISAM 表. FULLT

  • MySQL中索引与视图的用法与区别详解

    前言 本文主要给大家介绍了关于MySQL中索引与视图的使用与区别的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 索引 一.概述 所有的Mysql列类型都可以被索引. mysql支持BTREE索引.HASH索引.前缀索引.全文本索引(FULLTEXT)[只有MyISAM引擎支持,且仅限于char,varchar,text列].空间列索引[只有MyISAM引擎支持,且索引的字段必须非空],但不支持函数索引. MyISAM和InnoDB存储引擎的表默认创建BTREE索引,

  • MySQL索引背后的数据结构及算法原理详解

    MySQL索引背后的数据结构及算法原理详解

    摘要 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题.特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等.为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论. 文章主要内容分为三个部分. 第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础. 第二部分结合MySQL数据库中My

  • 简单谈谈Mysql索引与redis跳表

    简单谈谈Mysql索引与redis跳表

    摘要 面试时,交流有关mysql索引问题时,发现有些人能够涛涛不绝的说出B+树和B树,平衡二叉树的区别,却说不出B+树和hash索引的区别.这种一看就知道是死记硬背,没有理解索引的本质.本文旨在剖析这背后的原理,欢迎留言探讨 问题 如果对以下问题感到困惑或一知半解,请继续看下去,相信本文一定会对你有帮助 mysql 索引如何实现 mysql 索引结构B+树与hash有何区别.分别适用于什么场景 数据库的索引还能有其他实现吗 redis跳表是如何实现的 跳表和B+树,LSM树有和区别呢 解析 首先

  • 高效利用mysql索引指南

    前言 mysql 相信大部分人都用过,索引肯定也是用过的,但是你知道如何创建恰当的索引吗?在数据量小的时候,不合适的索引对性能并不会有太大的影响,但是当数据逐渐增大时,性能便会急剧的下降. 本篇是对 mysql 索引的一个归纳总结,如果有错误的地方,记得评论指出哦. 索引基础 我们都有都知道查字典的步骤,是先在索引页中找到这个字的页码,然后再到对应的页码中查看这个字的信息.mysql 的索引方法也是和这个类似的,先在索引中找到对应值,然后根据匹配的索引记录找到对应的数据行.假如有下面的 sql

  • Mysql索引选择以及优化详解

    Mysql索引选择以及优化详解

    索引模型 哈希表 适用于只有等值查询的场景,Memory引擎默认索引 InnoDB支持自适应哈希索引,不可干预,由引擎自行决定是否创建 有序数组:在等值查询和范围查询场景中的性能都非常优秀,但插入和删除数据需要进行数据移动,成本太高.因此,只适用于静态存储引擎 二叉平衡树:每个节点的左儿子小于父节点,父节点又小于右儿子,时间复杂度是 O(log(N)) 多叉平衡树:索引不止存在内存中,还要写到磁盘上.为了让一个查询尽量少地读磁盘,就必须让查询过程访问尽量少的数据块.因此,要使用"N 叉"

  • MySQL索引机制的详细解析及原理

    MySQL索引机制的详细解析及原理

    目录 一.索引的类型与常见的操作 二.常见的索引详解与创建 三.索引的原理 1.通过实验介绍B+tree 2.延伸 四.聚簇索引和非聚簇索引 1.使用聚簇索引的优势 2.什么情况下无法使用索引 总结 一.索引的类型与常见的操作 前缀索引 MySQL 前缀索引能有效减小索引文件的大小,提高索引的速度.但是前缀索引也有它的坏处:MySQL 不能在 ORDER BY 或 GROUP BY 中使用前缀索引,也不能把它们用作覆盖索引(Covering Index). 复合索引 集一个索引包含多个列(最左前

  • 图文并茂地讲解Mysql索引(index)

    图文并茂地讲解Mysql索引(index)

    目录 前言 1. 索引概述 1.1 什么是索引? 1.2 使用索引和不使用索引的区别 1.3 索引的特点 2. 索引结构 2.1 概述 2.2 二叉树 2.3 B-Tree 2.4 B+Tree 2.5 Hash 3.索引分类 3.1 索引分类 3.2 聚集索引&二级索引 4. 索引语法 5. SQL性能分析 5.1 SQL执行频率 5.2 慢查询日志 5.3 profile详情 5.4 explain 6. 索引使用 6.1 验证索引效率 6.2 最左前缀法则 6.3 索引失效情况 6.3.1

随机推荐