深圳网站优化企业,新化网站建设,ae成品免费下载网站,保险网站推荐InnoDB 是一种兼顾高可靠性和高性能的通用存储引擎#xff0c;在 MySQL 5.5 之后#xff0c;InnoDB 是默认的 MySQL 存储引擎。 InnoDB 对每张表在磁盘中的存储以 xxx.ibd 后缀结尾#xff0c;innoDB 引擎的每张表都会对应这样一个表空间文件#xff0c;用来存储该表的表结…InnoDB 是一种兼顾高可靠性和高性能的通用存储引擎在 MySQL 5.5 之后InnoDB 是默认的 MySQL 存储引擎。 InnoDB 对每张表在磁盘中的存储以 xxx.ibd 后缀结尾innoDB 引擎的每张表都会对应这样一个表空间文件用来存储该表的表结构frm、sdi、数据和索引。
存储结构
InnoDB 的逻辑存储结构表空间、段、区、页、行 InnoDB是以数据页为单位来读写数据的数据页大小默认是16KB每次从磁盘最少读取16KB的数据到内存或者刷新内存中16KB的数据到磁盘
数据页 文件头记录数据页的信息包括两个指针一个指向上一个数据页一个指向下一个数据页
每个数据页中存储了详细的记录数据 记录
UserRecord中存储了行记录这些记录会通过单向链表按照主键的顺序有小到大排列单向链表的检索效率比较低所以数据页中还有一个页目录结构帮助快速查找记录。数据页中的记录被分为若干组当然带有删除标识的不会参与分组每组中的记录也是按照主键从小到大排序每组中最后一条记录的主键值最大它的头信息中记录了本组的记录条数n_owned字段页目录记录了每组最大最后一条记录的地址偏移量叫做槽它相当于指针指向了不同组的最后一条记录。当我们检索数据页中的记录时由于记录都是按照主键大小排列的可以使用槽号进行二分法定位某个槽也就是定位到某一组然后比较该组的最大记录的主键值最终定位到某个槽。由于槽都是定位到每组最大的那条记录所以如果要定位到最小的那条记录可以通过查找上一个槽的最后一条记录然后沿着单向链表向后检索 为了减少在某个分组中检索的时间复杂度InnoDB规定了每个分组的大小
第一个分组只能有一条记录最后一个分组记录条数在1-8之间其余分组记录条数在4-8之间
B-树介绍
B-树也称为B树是一种平衡的多叉树。 阶数一个节点最多有多少个孩子节点。一般用字母m表示关键字节点上的数值就是关键字度一个节点拥有的子节点的数量。
一颗m阶的b-树根结点至少有两个子女每个非根节点所包含的关键字个数 j 满足⌈m/2⌉ - 1 j m - 1.(⌈⌉表示向上取整)有k个关键字(关键字按递增次序排列)的非叶结点恰好有k1个孩子。所有的叶子结点都位于同一层。B 树原理
B树是B-树的变体也是一颗多路搜索树 每个结点至多有m个子女;非根节点关键值个数范围m/2 k m-1相邻叶子节点是通过指针连起来的并且是关键字大小排序的。 ## 区别
B-树内部节点是保存数据的;而B树内部节点是不保存数据的只作索引作用它的叶子节点才保存数据。
B树相邻的叶子节点之间是通过链表指针连起来的B-树却不是。
查找过程中B-树在找到具体的数值以后就结束而B树则需要通过索引找到叶子结点中的数据才结束
B-树中任何一个关键字出现且只出现在一个结点中而B树可以出现多次。插入 流程 1.B树插入都是在叶子结点进行的就是插入前需要先找到要插入的叶子结点。 2.如果被插入关键字的叶子节点当前含有的关键字数量是小于阶数m则直接插入。 3.如果插入关键字后叶子节点当前含有的关键字数目等于阶数m则插该节点开始分裂为两个新的节点一个节点包含⌊m/2⌋ 个关键字另外一个关键字包含⌈m/2⌉个关键值。⌊m/2⌋表示向下取整⌈m/2⌉表示向上取整如⌈3/2⌉2。 4.分裂后需要将第⌈m/2⌉的关键字上移到父结点。如果这时候父结点中包含的关键字个数小于m则插入操作完成。 5.分裂后需要将⌈m/2⌉的关键字上移到父结点。如果父结点中包含的关键字个数等于m则继续分裂父结点。 参考https://juejin.cn/post/6929833495082565646?searchId20240301221957FB5B4942920DC0A4744E 查找 单值查询查找32 第一次磁盘 I/O查找磁盘块1即根节点36,43,因为32小于36因此访问根节点的左边第一个孩子节点 第二次磁盘 I/O, 查找磁盘块2即根节点的第一个孩子节点获得区间(28,32),遍历即可得32. 范围查询 [32,40] 第一步先访问根节点发现区间的左端点32小于36,则访问根节点的第一个左子树(28,32); 第二步访问节点28,32找到32于是开始遍历链表把[32,40]区间值找出来这也是B树比B-树高效的地方。 删除
找到包含关键值的结点如果关键字个数大于m/2直接删除即可找到包含关键值的结点,如果关键字个数大于m/2并且关键值是当前节点的最大小值并且该关键值存在父子节点中那么删除该关键字同时需要相应调整父节点的值。找到包含关键值的结点如果删除该关键字后关键字个数小于⌈m/2⌉并且其兄弟结点有多余的关键字则从其兄弟结点借用关键字找到包含关键值的结点如果删除该关键字后关键字个数小于⌈m/2⌉并且其兄弟结点没有多余的关键字则与兄弟结点合并。
常见问题 InnoDB一棵B树可以存放多少行数据 约2千万行 在计算机中磁盘存储数据最小单元是扇区一个扇区的大小是512字节。
文件系统中最小单位是块一个块大小就是4k
InnoDB存储引擎最小储存单元是页一页大小就是16k。如果一行记录的数据大小为1k那么单个叶子节点可以存的记录数 16k/1k 16.假设主键ID为bigint类型长度为8字节而指针大小在InnoDB源码中设置为6字节非叶节点的一条记录为8614字节可存放16k/14B 1170条因此一棵高度为2的B树能存放1170 * 1618720条这样的数据记录。同理一棵高度为3的B树能存放1170 *1170 *16 21902400也就是说可以存放两千万左右的记录。B树高度一般为1-3层已经满足千万级别的数据存储。 为什么索引结构默认使用B树而不是hash二叉树红黑树B-树 Hash哈希只适合等值查询不适合范围查询。 一般二叉树可能会特殊化为一个链表相当于全表扫描。 红黑树是一种特化的平衡二叉树MySQL 数据量很大的时候索引的体积也会很大内存放不下的而从磁盘读取树的层次太高的话读取磁盘的次数就多了。 B-Tree叶子节点和非叶子节点都保存数据相同的数据量B树更爱矮壮也是就说相同的数据量B树数据结构查询磁盘的次数会更少。 B-树和B树的区别 B-树内部节点是保存数据的;而B树内部节点是不保存数据的只作索引作用它的叶子节点才保存数据。B树相邻的叶子节点之间是通过链表指针连起来的B-树却不是。查找过程中B-树在找到具体的数值以后就结束而B树则需要通过索引找到叶子结点中的数据才结束B-树中任何一个关键字出现且只出现在一个结点中而B树同一个键值可在不同层级的节点中重复出现。 B树和红黑树的区别 B树的所有值都存在于叶子节点并且叶子节点之间通过指针连接形成一个有序链表。这种结构非常适合范围查询红黑树虽然在单个元素查找上有优势但需要进行额外的遍历才能完成范围查询。由于B树具有顺序访问的特性数据库系统可以利用预读优化来提高连续磁盘块的读取性能。而红黑树的结构不容易进行批量的顺序读取操作因此无法充分利用预读特性。B树通过将键和数据分离使得节点可以存放更多的键。这样就可以减少树的高度红黑树作为二叉树在存储大量数据时会占据更多空间因为每个节点只有两个子节点的指针。 为什么索引使用B树不使用跳表 磁盘I/O效率B树特别适合于磁盘存储的优化。它们能够最小化磁盘I/O操作因为一个节点通常对应一个磁盘块的大小这样可以减少读取数据时所需的磁盘访问次数。跳表在内存中运行效率较高但当涉及到磁盘操作时其性能可能会下降因为跳表的节点间隔是不规则的不一定能有效利用磁盘块的空间。 删除操作在B树中插入和删除操作可以更容易地保持树的平衡而且不需要重新组织整个数据结构。虽然跳表支持比较简单的插入和删除操作但在大量的更新操作后可能需要额外的工作来重新平衡。 存储利用率B树的节点通常设计为页大小以便与磁盘或文件系统页面对齐从而实现高效的空间利用。而跳表可能会因为其节点大小不一致而在某些情况下导致存储空间利用率不高。
