大纲在了解B树、B+树、AVL树、红黑树之前，我们先看一下各种树型结构的大致实际应用场景：B和B+树：主要用在文件系统以及数据库中做索引等AVL树：平衡二叉树之一，应用相对其他数据结构比较少，windows对进程地址空间的管理用到了AVL红黑树：平衡二叉树，广泛应用在C++STL中，比如map和set，Java的TreeMap树结构已经有了很多种形式，为何出现B树、B+树、AVL树、红黑树？下面我们按照这个大纲来看一下这些问题？二叉搜索树概念二叉搜索树(平衡二叉树)是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度。我们在二
在MySQL中，B+树被广泛应用于索引结构，因为它支持高效的范围查询和区间扫描，并且有助于减少磁盘I/O操作，从而提高查询效率。为什么MySQL使用B+树而不是B树？主要有以下几个原因：1、B+树可以更好地利用磁盘预读特性在数据库中，数据通常都存储在磁盘上。而磁盘的读写速度比内存慢很多，因此需要尽量减少磁盘I/O操作。B+树相对于B树来说，其内部节点只存储键值信息，而不存储数据信息，这样可以让每个节点能够存储更多的键值信息，从而使得查询同一层次的所有数据时，能够一次性读入更多的数据块，减少磁盘I/O操作。2、B+树能够更快地进行范围查询由于B+树的非叶子节点只存储键值信息，而不存储指向数据的指
⭐注意：不会直接讲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、
一、概述聚集索引：聚集索引是索引结构和数据一起存放的索引。类似于字典的正文，当我们根据拼音直接就能找到那个字。非聚集索引：非聚集索引是索引结构和数据分开存放的索引。类似于根据偏旁部首找字，首先找到该字所在的地址，再根据地址找到这个字的信息。二、建立索引sql建立聚簇索引使用CREATEINDEX语句，格式为：CREATECLUSTERINDEXindex_nameONtable_name(column_name1,column_name2,...);三、区别及优缺点区别：1.聚集索引一个表只能有一个，而非聚集索引一个表可以存在多个2.聚集索引存储记录是物理上连续存在，而非聚集索引是逻辑上的连续
一、概述聚集索引：聚集索引是索引结构和数据一起存放的索引。类似于字典的正文，当我们根据拼音直接就能找到那个字。非聚集索引：非聚集索引是索引结构和数据分开存放的索引。类似于根据偏旁部首找字，首先找到该字所在的地址，再根据地址找到这个字的信息。二、建立索引sql建立聚簇索引使用CREATEINDEX语句，格式为：CREATECLUSTERINDEXindex_nameONtable_name(column_name1,column_name2,...);三、区别及优缺点区别：1.聚集索引一个表只能有一个，而非聚集索引一个表可以存在多个2.聚集索引存储记录是物理上连续存在，而非聚集索引是逻辑上的连续
