二叉查找树的构建_二叉排序树的构造详细图

Mysql InnoDB索引结构 　　InnoDB索引结构支持那些类型 　　Storage EnginePermissible Index TypesInnoDBBTREEMyISAMBTREEMEMORY / HEAPHASH, BTREENDBHASH, BTREE (see note in text) ｜ 　　然后我们再看看 InnoDB的介绍功能表格特征支持B树索引是的备份/时间点恢复（在server中实现，而不是在存储引擎中。(通用的，binary log在server层中产生)）是的集群数据库支持不聚合索引是的压缩数据是的数据缓存是的全文检索索引是（MySQL 5.6 及更高版本提供对 FULLTEXT 索引的支持。）地理空间数据类型支持是的地理空间索引支持是（MySQL 5.7 及更高版本提供对地理空间索引的支持。）Hash索引否（InnoDB 在内部使用哈希索引来实现其自适应哈希索引功能。）索引缓存是的锁定粒度行MVCC是的复制支持（在服务器中实现，而不是在存储引擎中。(通用的，binary log在server层中产生)）是的存储限制64TBT-tree索引不事务是的更新数据字典的统计信息是的 　　可以发现InnoDB只支持B-Tree索引，至于Hash索引在内部使用 　　B树的结构是什么 　　

　　B树（B-tree）是一种一种自平衡树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构被应用于数据库和文件系统的实现上。 　　定义 　　一个m阶的B树是一个有以下属性的树：每一个节点最多有m个子节点每一个非叶子节点（除根节点）最少有⌈m/2⌉个子节点（这个特性使得B树中删除或插入新的值时可以用来调整树来保持树的特性。）如果根节点不是叶子节点，那么它至少有两个子节点有k个子节点的非叶子节点拥有k-1个键所有叶子节点都在同一层 　　每一个内部节点的键将节点的子树分开。例如如果一个内部节点有3个子树节点（子树），那么它必须有两个键：a1和a2。左子树的所有值都必须小于a1，中间子树的所有值都必须在a1和a2之间，右边子树的所有值都必须大于a2。 　　一些平衡树只在叶子节点存储值，而且叶子节点和内部节点使用不同的结构。B树在每一个节点中都存储值，所有节点都有相同的结构。然而叶子节点没有子节点，所以可以通过使用专门的结构来提升B树的性能。 　　复杂度 　　算法平均最差空间O(n)O(n)搜索O(log n)O(log n)插入O(log n)O(log n)删除O(log n)O(log n) 　　运用理念 　　保持了值有序，以顺序遍历使用层次化的索引来最小化磁盘读取使用不完全填充的块来加速插入和删除通过优雅的遍历算法来保持索引平衡 　　另外，B树通过保证内部节点至少半满来优化最小空间浪费。一颗B树可以任意数目的插入和删除。 　　弊端 　　除非重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。 　　变体 　　术语B树可以指定一个特定的方案，可以指定大体上一类方案。狭义上，一个B树在它内部节点中存储键值，但不需要在叶节点上存储这些键值的记录。大体上的一类包括一些变体，如B+树和B*树。 　　下面我们继续了解B+树。 　　B+树的结构是什么 　　

　　B+树是一种数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入和修改拥有较稳定的对数时间复杂度。B+树素自定向上插入，这与二叉树恰好相反。 　　B+树在节点访问时间远远超过节点内访问时间的时候，比可以作为替代实现有着实在的优势。这通常在多数节点在此级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或者近似的大小。 　　B+背后的想法是内部节点可以有在预定范围内的可变数量目的子节点。因此，B+树不需要像其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树（常简称为2-3 树）中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。 　　定义 　　在B+树中的节点通常被表示为一组有序的素和子针树。 　　一个m阶的B+树是一个有以下属性的树：除根节点外的每个节点都包含最少⌊m/2⌋个素，最多m-1个素对于任意的节点最多有m个子指针。所有内部节点，子指针的数目总比素的数目多一个。所有叶子都在同一高度，叶节点本身按照关键字大小从小到大链接。 　　注意： 　　这里的M表示一个节点最多能有m个子节点而不是树的阶层，也就是每个节点上最多的素个数。上图的M为4，所以最多有4个子树，最多有3个素。最多子树肯定比最多素大1。 　　查找 　　查找以典型的方式进行，类似二叉查找树。起适于根节点，自顶向下遍历树，选择要分离值的任意一边的子指针。在节点内部典型的使用二分查找来确定这个位置。 　　插入 　　节点要处于违规状态，它必须包含在可接受范围之外数目的素。首先，查找要插入其中的节点位置。接着把值插入这个节点中。如果没有节点处于违规状态则处理结束。如果某个节点有过多素，则把它分裂成为两个节点，每个都有最小数目的素。在树上递归向上继续处理直到达根节点，如果根节点被分裂，则创建一个新的根节点。为了使它工作，素的最小和最多数目典型的必须选择为最小数不小于最大数的一半。 　　删除 　　首先，查找要删除的值，接着从包含它的节点中删除这个值。如果没有节点处于违规状态则处理结束。如果节点处于违规状态则有两种可能情况：它的兄弟节点，就是同一个父节点的子节点，可以把一个或者多个它的子节点转移到当前节点，则把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续处理这个直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而去合并后的节点成为新的根节点。 　　B+树和B树的结构对比 　　树类型任意节点内部节点（非叶子节点（除根节点）)根节点叶子节点B树每一个节点最多有m个子节点(一样)每一个非叶子节点（除根节点）最少有⌈m/2⌉个子节点；有k个子节点的非叶子节点拥有k-1个键如果根节点不是叶子节点，那么它至少有两个子节点；有k个子节点的非叶子节点拥有k-1个键所有叶子节点都在同一层B+树对于任意的节点最多有m个子指针(一样)所有内部节点，子指针的数目总比素的数目多一个；除根节点外的每个节点都包含最少⌊m/2⌋个素，最多m-1个素所有叶子都在同一高度，叶节点本身按照关键字大小从小到大链接；除根节点外的每个节点都包含最少⌊m/2⌋个素，最多m-1个素 　　需要注意的是：B+树是是B树的变形，所以B+根节点也需要符合B树根节点的要求。 　　可以发现，B+树和B树的区别不大。除了内部节点最少的要求素个数比B树更加严格（最多多一个），同时最多为m-1个；叶子节点也比B树更加严格，需要包含所有关键字、从小到大链接、最少包含⌊m/2⌋个素，最多m-1个素。 　　Hash索引的结构是怎样的？（自适应hash索引） 　　上文已经提到InnoDB索引不支持Hash结构索引，但是在内部使用哈希索引来实现自适应哈希索引功能。下面我们简单了解一下。 　　自适应索引InnoDB主要用来帮助B+树索引对经常访问的索引使用索引的前缀构建哈希索引，key就是hash,value为指向索引值（索引叶节点）的指针。 　　InnoDB具有监视索引搜索的机制，如果InnoDB主要到查询可以构建哈希索引中受益，就会自动这样做。 　　但是在并发比较高的情况下，对自适应哈希索引的访问有时会变成竞争资源；同时哈希只能定位明确的值。所以可以根据情况对innodb_adaptive_hash_index_parts变量进行设置开启或关闭，MySql8.0是默认开启的。 　　为啥索引结构使用B+树，不用B树，Hash、二叉树、平衡二叉树、红黑树？ 　　为啥不用Hash呢？ 　　Hash只能根据关键字计算Hash映射，适合等值查询，不能比较大小进行范围查询，不能部分查询，不能排序、必须回表不能直接使用索引返回结果或者连接、hash会重复并且相同的键如果存在大量重复键值的情况需要大量回表。 　　为啥不用二叉树呢？ 　　直接和平衡树比较，二叉树不能自平衡，数据划分不均匀，查询效率不稳定还容易出现极端情况，所以还不如考虑平衡二叉树。 　　为啥不用平衡二叉树呢？ 　　一个节点只能存储一个关键字不利于使用较完整块的存储，无法充分发挥磁盘顺序读和预读的高效性；一个节点最多两个子树，数据量大的情况下树的阶层会很深，不便于从磁盘中读取和构造树；同时需要动不动就为了维护平衡对树结构进行调整效率不高。 　　平衡二叉树，如果遇到极端情况，每次插入的数据都比上一次插入的数据大，这样就成了单链树，时间复杂度为O(N)。 　　为啥不用红黑树呢？ 　　红黑树比起平衡二叉树维护树的成本稍低（不需要动不动就为了维护平衡对树结构进行调整），但是拥有平衡二叉树的缺点。 　　为啥不用B树呢？ 　　通过上面B树和B+树的对比，可以发现B+树比B树更加严格是有好处的：同时最多为m-1个，不会导致内部节点过多。叶节点包括所有关键字便于直接从叶子节点中拿去批量数据。叶节点从小到大，便于排序和按序查找。 　　组合索引结构是怎样的？ 　　组合索引底层数据结构还是B+树，只不过多个列组成B+树子节点的关键字而已，比如有A、B、C三个字段组成组合索引，那么关键字的顺序是先A后B最后C，也就是说只有A相同的情况下B才会有序，A、B都相同的情况下C才会有序，其实很好理解，就像一个字符串比较大小一样，只有不管字符串多长前面的字符决定了顺序。 　　大致结构如下图，下图是姓、名、出生年份组成的组合索引。

　　聚簇索引和非聚簇索引的结构区别？ 　　

　　从上图就能看的出来，InnoDB聚合索引和非聚合索引的区别。 　　聚簇索引 　　在InnoDB中聚簇索引指的并不是单独的索引类型，底层结构还是B+树，只不过叶子节点中存放整个行数据，和MyISAM的区别一目了然（索引结构和数据存储分离）。这就说明使用InnoDB的话一个表中只能有一个聚簇索引，一般是主键，如果没有主键则使用第一个唯一索引，如果都没InnoDB就创建一个隐式的聚簇索引-Row ID占6个字节。 　　非聚簇索引 　　非聚簇索引也称为二级索引，如上图的辅助键索引，叶子节点除了有索引列还有主键列值。查询数据行需要根据叶节点的主键值去走聚簇索引拿到数据行。 　　给出数据量怎么计算B+树索引层级？ 　　首先我们要知道，不同类型对应的字段占几个字节、索引指针占几个字节、InnoDB一页占几个字节。 　　不同类型的字段占几个字节怎么计算？ 　　下面给出常用的tinyint：1个字节int：4个字节bigint：8个字节datetime：8个字节varchar：根据编码（latin1编码的，一个字符占用一个字节，gbk编码的，一个字符占用两个字节，utf8编码的，一个字符占用三个字节)，一般用utf8加上1-2个表示长度的字节。char：根据编码（latin1编码的，一个字符占用一个字节，gbk编码的，一个字符占用两个字节，utf8编码的，一个字符占用三个字节)，一般用utf8加上。decimal(M,D)：常用的decimal(10,2)占5个字节。 　　索引指针占几个字节？ 　　官方文档显示： 　　索引占6个字节，也就是2^48=256T，很足够了。 　　InnoDB一页占几个字节？ 　　官方文档默认为16个字节。 　　InnoDB B+树对节点内部的子节点数目最大控制是多少？ 　　笔者暂时没找到，或许因为索引关键字字段类型长度不一样比较难定义，直接按照page size进行约束了。 　　有知道的笔者可以评论留言，笔者再进行更新。 　　计算 　　我们可以计算常用的bigint自增主键，两层能使用B+数组织多少行数据，假设一行数据占1k。一页能放16行数据索引子节点占8（bigint）+6（指针）=14个字节，因为b+树素+1等于指针数。设一页能x个指针，那么8*(x-1)+6x=16*1024，x向下取证的结果是1170。所以一页能放约1170个指针。 　　因此如果是两层那么就是16*1170=18720行数据。（一万多）如果是三层那么就是=行数据。（两千多万）如果是四层那么就是*1170=行数据。（256亿多） 　　3-4层能满足绝大多数场景，达到4层就需要开始考虑分库分表了，层数越多B+树的效率也会越低，也更加消耗资源。 　　关于 MySQL 问题（事务、acid 特性、脏读、复读、幻读、死锁、集群） 　　MySQL 系统性学习：索引B+树，最左匹配，覆盖索引，索引优化 　　C/C++Linux服务器开发/高级架构师 系统性学习公开课 　　LinuxC/C++服务器开发/架构师面试题、学习资料、教学视频和学习路线图，有需要的可以自行添加学习交流群