⭐注意：不会直接讲B+树的结构，会从最简单的二叉树开始讲起来。如果认真看完，我想你对树类型的数据结构的理解又上了一个新的台阶。⭐如果有误，请大家指出。下文均是在B站学习的过程中，总结的笔记和心得体会索引结构MySQL索引是在存储引擎层实现的，不同的存储引擎层，有不同的索引结构，主要包含四种索引：名称简介B+树索引最常见的索引类型Hash索引底层是由哈希表实现（⭐性能很强，但是！不支持范围查询）空间索引（R-tree）是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型全文索引（Full-text）通过建立倒排索引方式，来快速匹配文档。我们会从二叉树到B+树1、二叉树二叉树，实际上就是
文章目录一、B-树1.常见的搜索结构2.B树概念3.B-树的查找4.B-树的插入分析二、B+树和B*树1.B+树2.B*树三、B-树的应用1.索引2.MySQL索引简介2.1MyISAM2.2InnoDB一、B-树1.常见的搜索结构种类数据格式时间复杂度顺序查找无要求O(N)二分查找有序O(log2N)二叉搜索树无要求O(N)二叉平衡树(红黑树和AVL树)无要求O(log2N)哈希无要求O(1)以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘上，有需要搜索某些数据，那么如果
mysql的innodb的索引的B+树逐步讲解B树B+树B树和B+树的不同点聚集索引VS非聚集索引总结（面试题）1.为什么不使用二叉查找树？2.为什么不使用平衡二叉树？3.为什么不使用B树？4.为什么MySQL选择B+树做索引B+树：是由二叉查找树，平衡二叉树和B树演化而来二叉查找树：任何节点的左节点的值都小于该节点，右节点都大于该节点。为了避免二叉查找树的极端情况，即太高瘦，引入了平衡二叉树。平衡二叉树：又称AVL树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过1。不平衡的时候会通过调整节点进行平衡，即要矮胖。二叉查找树和平衡二叉树较为熟悉，不详细说，主要记录B树和B
B树是什么？B树是一种多路平衡查找树平衡，指的是子树高度相同（即所有叶子结点均在同一层），即每个结点的平衡因子均等于0多路，就是它除了根结点外（之所以根结点的分叉数不限定，是因为当整棵树只有1个关键字，根结点只能有2个分叉），其余每个结点都至少有m/2向上取整个分叉。（m是它的阶，同时m也是结点的最大分叉数，也可以理解为每个结点最多有m棵子树）（1）所有结点中，拥有孩子个数最多的，也就是分叉数最大值，称为整棵B树的阶。例如：结点最多有3个分叉，则称为3阶B树（2）每个结点中包含的多个数据元素，称之为“关键字”，当某个结点有m棵子树的时候，则一定有m-1个关键字。如下图中有3个分叉的结点，只能在
B树B树是一种自平衡的搜索树，广泛应用于文件系统和数据库中。B树的特点是：根节点至少有两个子节点；除根节点和叶子节点外，每个节点至少有m个子节点，其中m称为B树的阶；所有叶子节点都在同一层；每个节点存储的关键字个数必须满足：$$\lceil\frac{m}{2}\rceil-1\leqslantn\leqslantm-1$$其中，n为该节点存储的关键字个数。B树相比于二叉搜索树，能够更快地进行查找、插入、删除等操作，因为B树每个节点可以存储多个关键字，而不是只能存储一个。B+树B+树是在B树的基础上进行了优化，也是一种自平衡的搜索树，常用于数据库和操作系统的文件系统中。B+树和B树的区别在于：
目录一、索引初识和测试数据的构建二、磁盘三、MySQL、OS、磁盘的交互方式（InnoDB存储引擎）四、MySQL中索引和page的理解1、为什么MySQL和磁盘进行IO交互的时候，要采用page的方案进行交互，而不是采用用多少，加载多少的方式？2、MySQL对page的管理方式2.1先来看个错误page的数据结构2.2单个page内部的正确的数据结构2.3多个page之间的正确的数据结构2.4B+树的特征 2.5MySQL的主键2.6为什么B+树做索引优于其他数据结构？2.7聚簇索引和非聚簇索引2.7.1MyISAM的辅助（普通）索引2.7.2innodb的辅助（普通）索引五、索引的操作1、
目录引言介绍树结构树结构的基本概念树结构的特点和层次关系树结构在实际问题中的应用二叉树二叉树的定义和特点二叉树的遍历方式二叉树的应用B树B树的基本概念和特点B树的结构和优势B树的应用B+树B+树相对于B树的优势和特点B+树的结构和查询性能B+树的应用B*树B*树的定义和特点B*树的结构和优势B*树的应用比较与总结二叉树、B树和B+树的对比不同树结构的适用场景和优势结论引言树结构是计算机科学中广泛应用的一种数据结构。它以其层次化的组织方式和多样的变体，在各个领域中发挥着重要作用。本文将从多个角度深入探讨树结构及其应用，包括二叉树、B树、B+树和B*树的基本概念、特点、遍历方式、应用场景以及优势和
前言本文章收录在MySQL性能优化+原理+实战专栏，点击此处查看更多优质内容。本文摘录自▪小孩子4919《MySQL是怎样运行的：从根儿上理解MySQL》我们上一篇文章详细的了InnoDB存储引擎的B+树索引，我们必须知道下边这些结论：每个索引都对应1棵B+树，B+树分为好多层，最下边一层是叶字节点，其余的是内节点（非叶子节点）。所有用户户记录都存储在B+树的叶子节点，所有目录项记录都存储在内节点。InnoDB存储引擎会自动为主键（如果没有它会自动帮我们添加）建立聚簇索引，聚簇索引的叶子节点包含完整的用户记录。我们可以为自己感兴趣的列建立二级索引，二级索引的叶子节点包含的用户记录由索引列+主键
例如，我有以下b树模型，每个节点都包含标签/值对。树表示优先级(或优先级)，根最高，叶子最低(但这是特定于应用程序的)。我想将一个新的树部分合并到父节点中，新部分包含潜在的公共(public)标记/值对，一直向下到叶节点上方的节点(完全重复的新树部分不会被合并)。例如指示的现有树(标记、值)对:A,0,----------,-------------,B,1B,2B,3,-------------,C,1C,2要合并的新树:A,0|B,3,-----------,C,1C,2最终合并树:A,0,----------,-----------------,B,1B,2B,3,-------
在B+树的常见实现中，我们可以假设键具有固定长度(例如25字节)。然后我们可以定义每个节点必须有最少数量的键和最多数量的键。如果我想让树接受可变长度的键，我应该修改什么？如果我说节点必须至少有2个key，但我要插入的key太大以至于无法放入包含该节点的block中怎么办？ 最佳答案 简单的解决方案是将键存储为指针(包装在覆盖相对运算符等的类型中)而不是值，但这当然会破坏局部性，而局部性是使用B+树的一部分。也就是说，项目越大，项目在内存中相邻的重要性就越小。巨大的项目甚至一个缓存页面都放不下，更不用说同一页面中的多个项目了。另一种相
