解读MySQL中一个B+树能存储多少数据

目录
  • MySQL中一个B+树能存储多少数据
    • MySQL聚簇索引的存储结构
  • MySQL中B树与B+树的区别
    • B树
    • B+树
    • B树与B+树的区别
  • 总结

MySQL中一个B+树能存储多少数据

MySQL聚簇索引的存储结构

MySQL中InnoDB页的大小默认是16k。也可以自己进行设置。（计算机在存储数据的时候，最小存储单元是扇区，一个扇区的大小是 512 字节，而文件系统（例如 XFS/EXT4）最小单元是块，一个块的大小是 4KB。

InnoDB 引擎存储数据的时候，是以页为单位的，每个数据页的大小默认是 16KB，即四个块。）

在B+树中，一个结点就是一页。非叶子结点由主键值和一个指向下一层的地址的指针组成的组合组成。叶子结点中由一组键值对和一个指向该层下一页的指针组成，键值对存储的主键值和数据。

由存储结构，可以大概计算出一个B+树能存储的数据数量。

指针在InnoDB中为6字节，设主键的类型是bigint，占8字节。一组就是14字节。

计算出一个非叶子结点可以存储16 * 1024 / 14 = 1170个索引指针。

假设一条数据的大小是1KB，那么一个叶子结点可以存储16条数据。

得出两层B+树可以存储1170 x 16 = 18720 条数据。

三层B+树可以存储1170 x 1170 x 16 = 21902400条数据。

MySQL中B树与B+树的区别

B树

B树和B+树都是应用在数据库索引上，可以认为是m叉的多路平衡查找树，但是理论上讲，二叉树的查找速度和比较次数都更小，为什么不用二叉树呢？

这是因为我们要考虑磁盘IO的影响，它相对于内存来说是很慢的，数据库索引是存储在磁盘上的，当数据量很大时，就不能把整个索引全部加载到内存中，只能逐一加载每一个磁盘页（对应索引树的节点）。

所以我们要减少IO的次数，对于树来说，IO次数就是树的高度，而“矮胖”就是B树的特征之一。

B树的特征：

  • 关键字集合分布在整颗树中；
  • 任何一个关键字出现且只出现在一个结点中；
  • 搜索有可能在非叶子结点结束；
  • 其搜索性能等价于在关键字全集内做一次二分查找；

B+树

B+树是B树的变体，是一种查询性能更好的B树。B+树是一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各叶结点指针进行连接。

B+树的特征：

  • 有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）。
  • 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
  • 所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。
  • 通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
  • 同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。

B树与B+树的区别

  • B树的中间节点保存节点和数据，B+树的中间节点不保存数据，数据保存在叶子节点中；所以磁盘页能容纳更多的节点元素，更“矮胖”；
  • B树的查找要只要匹配到元素，就不用管在什么位置，B+树查找必须匹配到叶子节点，所以B+树查找更稳定；
  • 对于范围查找到说，B树要从头到尾查找，而B+树只需要在一定的范围内的叶子节点中查找就可以；
  • B+树的叶子节点通过指针连接，从左到右顺序排列；
  • B+树的非叶子节点与叶子节点冗余；

总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

赞 (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 B+树索引与哈希索引详解

    关于MySQL B+树索引与哈希索引详解

    目录 索引介绍 B+树索引 优点 缺点 哈希索引 优点 缺点 补充:二者区别 总结 索引介绍 索引是一种特殊的数据库结构,被设计用来快速查询数据库表中的特定记录.索引有多种类型,就像字典有拼音查找和偏旁查找一样都是为了提高检索效率.MySQL中最常见的索引类型有B+树索引 和 哈希索引,下面来简单介绍一下这两种索引类型有哪些差别和优劣. B+树索引 B+树索引是一种多路径的平衡搜索树,具有如下特点: 1.非叶子节点不保存数据,只保存索引值 2.叶子节点保存所有的索引值和数据 3.同级节点通过指针

  • MySQL中B树索引和B+树索引的区别详解

    MySQL中B树索引和B+树索引的区别详解

    目录 1.多路搜索树 2.B树-多路平衡搜索树 3.B树索引 4.B+树索引 总结 如果用树作为索引的数据结构,每查找一次数据就会从磁盘中读取树的一个节点,也就是一页,而二叉树的每个节点只存储一条数据,并不能填满一页的存储空间,那多余的存储空间岂不是要浪费了?为了解决二叉平衡搜索树的这个弊端,我们应该寻找一种单个节点可以存储更多数据的数据结构,也就是多路搜索树. 1. 多路搜索树 1.完全二叉树高度:O(log2N),其中2为对数,树每层的节点数: 2.完全M路搜索树的高度:O(logmN),其

  • 解读MySQL中一个B+树能存储多少数据

    目录 MySQL中一个B+树能存储多少数据 MySQL聚簇索引的存储结构 MySQL中B树与B+树的区别 B树 B+树 B树与B+树的区别 总结 MySQL中一个B+树能存储多少数据 MySQL聚簇索引的存储结构 MySQL中InnoDB页的大小默认是16k.也可以自己进行设置.(计算机在存储数据的时候,最小存储单元是扇区,一个扇区的大小是 512 字节,而文件系统(例如 XFS/EXT4)最小单元是块,一个块的大小是 4KB. InnoDB 引擎存储数据的时候,是以页为单位的,每个数据页的大小

  • mysql中的utf8与utf8mb4存储及区别

    目录 一.如何设置utf8mb4 二.问题 1.为什么存储的时候要区分utf8和utf8mb4 2.为什么读取的时候要区分utf8和utf8mb4 一.如何设置utf8mb4 mysql中针对字符串类型,在设置charset的时候可以精确到字段. 如果只将某个字段设置utf8mb4,那么其他字段不会受影响. 如果针对表来设置,那么已经存在的字段依然是utf8,并且会多出utf8的标记,之后所创建的字段才会是utf8mb4. 如果针对库来设置,那么已经存在的表依然是utf8,之后所创建的表才会是u

  • Mysql中批量替换某个字段的部分数据(推荐)

    MYSQL中批量替换某个字段的部分数据,具体介绍如下所示: 1.修改字段里的所有含有指定字符串的文字 UPDATE 表A SET 字段B = replace(字段B, 'aaa', 'bbb') example: update table set url= replace(url, 'aaa', 'bbb') [将url字段中的aaa批量更改为bbb] update table set url= REPLACE (url,'3','1.png') where 条件; 2.常规条件修改: upda

  • 详细解读MySQL中的权限

    详细解读MySQL中的权限

    一.前言 很多文章中会说,数据库的权限按最小权限为原则,这句话本身没有错,但是却是一句空话.因为最小权限,这个东西太抽象,很多时候你并弄不清楚具体他需要哪些权限. 现在很多mysql用着root账户在操作,并不是大家不知道用root权限太大不安全,而是很多人并不知道该给予什么样的权限既安全又能保证正常运行.所以,本文更多的是考虑这种情况下,我们该如何简单的配置一个安全的mysql.注:本文测试环境为mysql-5.6.4 二.Mysql权限介绍 mysql中存在4个控制权限的表,分别为user表

  • MySQL中的布尔值,怎么存储false或true

    MySQL中的布尔值,怎么存储false或true

    MySQL布尔值,存储false或true 简明说,数据库存储的布尔值是0和1,相当于一个字节的INT型整数 具体操作 如果是可视化界面,可以直接选择Boolean,长度设置为1.其最终显示的效果等价于TINYINT(1) 所以,zero == false:nonzero == true MySQL数据库存储布尔值 在Java编程中,我们经常会遇到将boolean值写入到mysql数据库的情况.但是,mysql数据库是没有boolean类型的,它的boolean值是用数字0和1来表示的. 下面,

  • mysql中一个普通ERROR 1135 (HY000)错误引发的血案

    今天接到测试人员反应,测试环境前端应用程序无连接mysql数据库,登录mysql服务器,查看错误日志,发现有如下报错: ERROR 1135 (HY000): Can't create a new thread (errno 11);if you are not out of available memory,you can consult the manual for a possible OS-dependent bug 第一反应感觉可能是跟ulimit限制连接数有关,文件描述符不够用.接下

  • 详细解读MySQL中COUNT函数的用法

    MySQL的COUNT函数是最简单的功能,非常有用的计算,预计由一个SELECT语句返回的记录数. 要了解COUNT函数考虑的EMPLOYEE_TBL的的表具有以下记录: mysql> SELECT * FROM employee_tbl; +------+------+------------+--------------------+ | id | name | work_date | daily_typing_pages | +------+------+------------+----

  • 解读mysql中的null问题

    解读mysql中的null问题

    目录 mysql的null问题 SQL中的NULL你真的懂了吗? 查询某列值为 NULL 的数据 NULL 是「未知」 三元逻辑(原文为 Ternary Logic) NOT IN 和 NULL mysql的null问题 (1) 使用统计函数的时候会出现null值得情况 注意点 sum avg max min 都有可能出现为null的问题 而且 sum avg max min count(具体字段) 都会忽略null的数据 count(*) 不会忽略null数据 (2) 使用count统计需要注

  • MySQL中使用innobackupex、xtrabackup进行大数据的备份和还原教程

    大数据量备份与还原,始终是个难点.当MYSQL超10G,用mysqldump来导出就比较慢了.在这里推荐xtrabackup,这个工具比mysqldump要快很多. 一.Xtrabackup介绍 1.Xtrabackup是什么 Xtrabackup是一个对InnoDB做数据备份的工具,支持在线热备份(备份时不影响数据读写),是商业备份工具InnoDB Hotbackup的一个很好的替代品. Xtrabackup有两个主要的工具:xtrabackup.innobackupex 1.xtraback

  • MySQL中order by的执行过程

    MySQL中order by的执行过程

    目录 一 .测试数据 二. 全字段排序 三.rowid 排序 四.全字段排序 与 rowid 排序 比较 前言: 在开发过程中,一定会经常碰到需要根据指定的字段排序来显示结果的需求.还是以前文的订单表为例,假设查询“张三”的所有订单,并且按照订单价格排序返回前 1000 个订单号以及价格. 一 .测试数据 测试的这个订单表my_order的结构是这样的: CREATE TABLE `my_order` ( `id` int(11) NOT NULL AUTO_INCREMENT, `oid` v

随机推荐