前言当我们发现SQL执行很慢的时候，自然而然的就会想到加索引。对于范围查询，索引的底层结构是B+树。今天就一起来学习一下B+树吧~树简介，树型B-tree，B+树简介，是一种数据结构。它由有限数量的节点组成一个具有层次关系的集合。因形似树而得名。一棵普通的树如下：一棵树是一个有限集，包含n（n为大于0的整数）个节点和n-1条边。它具有以下特点：每个节点没有子节点或只有有限的子节点；有一个特殊的节点，它没有父节点，称为根节点；每个非根节点只有一个父节点；树中没有环关于树的一些概念：结点度：一个结点包含的子结点的个数，称为该结点的度；树的度：在一棵树中，最大节点的度称为树的度；父节点：如果一个节点包含子节点，则称这个节点为它的子节点的父节点；depth：对于任意节点n，n的深度是从根到n的唯一路径的长度，根节点的深度为0；height：对于任意节点n，n的高度是从n到一片叶子的最长路径的长度，所有叶子的高度都为0；树的种类按顺序可分为有序树和无序树：无序树：树中任意节点的子节点之间没有顺序关系。有序树：树中任意节点的子节点之间存在顺序关系。根据节点包含的子树的个数，可以分为B树和二叉树。二叉树可分为以下几种类型：二叉树：每个节点最多有两个子树的树称为二叉树；二叉搜索树：首先，它是一棵二叉树。如果左子树不为空，则左子树上所有节点的值都相同。小于其根节点的值；如果右子树不为空，则右子树上所有节点的值都大于其根节点的值；左右子树也是二叉排序树；满二叉树：除叶节点外的所有节点都包含两个子树的树称为满二叉树；完全二叉树：如果一棵二叉树去掉最后一层节点，它就是一棵完全二叉树，最后一层的节点从左到右依次分布哈夫曼树：带权路径最短的二叉树。红黑树：红黑树是一种特殊的二叉搜索树，每个节点都是黑色或红色，根节点和叶子节点都是黑色。如果一个节点是红色的，它的孩子一定是黑色的。平衡二叉树（AVL）：一棵空树或其左右子树的高度差的绝对值不超过1，左右子树都是平衡二叉树B-tree，B+树介绍B-tree简介B-Tree，又称B-tree，是一种平衡的多叉树（可以类比为平衡二叉搜索树），更适合外部搜索。看看这些概念：顺序：一个节点最多有多少个子节点。（一般用字母m表示）Keyword：节点上的值为关键字Degree：一个节点拥有的子节点的个数。m阶B树具有以下特点：根节点至少有两个孩子；每个非根节点包含的关键字j个数满足：?m/2?-1<=j<=m-1。（??表示向上取整）一个有k个关键字的非叶子节点（关键字排列按递增顺序）恰好有k+1个孩子。所有叶节点都位于同一层。一个简单的B树如下：B+树简介B+树是B树的变种，也是一种多路搜索树。一棵m阶B+树主要有这些特点：每个节点至多有m个子节点；非根节点的键值范围：?m/2?-1<=k<=m-1相邻的叶子节点之间用指针连接，按关键字大小排序。三阶B+树如下：B+树和B-tree的主要区别如下：B-tree存储数据的内部节点；而B+树的内部节点不存储数据，只作为索引，其叶子节点保存数据。B+树的相邻叶子节点是通过链表指针连接起来的，而B-树则不是。在查找过程中，B-tree在找到具体值后结束，而B+树在结束前需要通过索引找到叶子节点中的数据。B-tree中的任何关键字出现并且只出现在一个节点中。B+树可以出现多次。B+树插入B+树插入要记住这些步骤：1.B+树插入是在叶子节点处进行的，即在插入之前，需要找到要插入的叶子节点。2、如果插入关键字的叶子节点当前包含的关键字个数小于阶m，则直接插入。3.如果插入关键字后，叶子节点当前包含的关键字个数等于阶m，则插入，节点开始“分裂”成两个新的节点，一个节点包含?m/2?个关键字，另一个A关键字包含?m/2?键值。（?m/2?表示向下取整，?m/2?表示向上取整，如?3/2?=2）。4.拆分后，?m/2?的关键字需要向上移动到父节点。如果此时父节点包含的关键字个数小于m，则插入操作完成。5.拆分后，?m/2?的关键字需要向上移动到父节点。如果父节点包含的关键字个数等于m，则继续拆分父节点。以4阶B+树为例。对于订单4，最多有3(m-1)个键值。假设你插入如下数据43、48、36、32、37、49、28.1。在空树中插入43。这时候根节点就是一个键值。这时候就是根节点和叶子节点。2.依次插入48和36。这时候后面的节点有3个关键字，已经满了。3、继续插入32，发现当前节点关键字不小于4阶，于是拆分?4/2?=2(下标0,1,2)，即43向上移动到父节点节点。4.继续插入37、49，之前的节点关键字没有满，直接插入，如下：5.最后插入28，发现当前节点关键字不小于4阶，于是拆分，再拆分，先?4/2?=2，也就是36向上移到父节点，因为父子节点只有2个key值，还是小于4，所以没必要继续分裂，insert完成B+树的查找，因为B+树的数据在叶子节点上，内部节点只是起到指针索引的作用，所以查找过程需要查找叶子节点。我们以这颗B+树为例：B+树单值查询假设我们要查询的值是32，第一次磁盘I/O，寻找磁盘块1，也就是根节点(36,43)，因为32小于36，所以访问根节点左边第一个子节点的第二个磁盘I/O，查找磁盘块2，也就是根节点的第一个子节点，得到区间(28,32)，遍历得到32。动态图如下：B+树区间查询假设我们要求区间[32,40]的值。第一步访问根节点，发现区间32的左端点小于36，则访问根节点的第一个左子树(28,32)；第二步，访问节点(28,32)，找到32，然后开始遍历链表，找出区间值[32,40]，这也是B+树比B树高效的地方.B+树删除B+树删除关键字，在这些情况下查找包含关键字值的节点。如果关键字个数大于?m/2?-1，直接删除即可；查找包含键值的节点，如果关键字个数大于?m/2?-1，且键值为当前节点的最大（最小）值，且该键值存在于父子节点中，然后删除关键字并相应地调整父节点的值。查找包含键值的节点。如果删除关键字后关键字个数小于?m/2?，且其兄弟节点有冗余关键字，则从其兄弟节点借用关键字找到包含键值的节点如果关键字个数小于?m/2?删除关键字后，其兄弟节点没有冗余关键字，则与兄弟节点合并。如果关键词数量大于?m/2?，直接删除即可；假设有这么一个5阶B+树，如果删掉22，因为关键字个数3>?5/2?-1=2，直接删除（??表示向上取整）如果关键字个数为大于?m/2?-1，且删除的关键字存在于父子节点中，则需要相应调整父子节点的值。如果删除20，因为关键字个数为3>?5/2?-1=2，而20是当前节点的边界值，存在于父子节点中，所以删除后，父子节点子节点也应相应调整。如果删除关键字后，关键字个数小于?m/2?-1，则兄弟节点可以借用下面的5阶B+树。如果删除15，则删除关键字的节点只剩下1个关键字。小于?5/2?-1=2，不满足B+树的特性，但是它的兄弟节点有3个元素（7,8,9），可以借用9，如图：删除关键字后，如果导致其他结点的关键字个数不足，又不必借用兄弟结点，则需要合并兄弟结点以下的5阶B+树：如果关键字7被删除，被删除关键字的节点只剩下1个关键字，小于?5/2?-1=2，不满足B+树的特性，不能借兄弟节点，所以发生merge，如下：主要流程是姜子：因为删除7后，只有8个关键字，不满足B+树特性(?m/2?-1<=关键字<=m-1)。并且没有兄弟键借用，所以8与前面的兄弟组合。被删除关键字节点的父节点，7索引也被删除，只留下一个9，其右兄弟节点(18,20)只有两个关键字，没有借用，所以在这里合并。被删除关键字节点的父子节点也与其兄弟节点合并后，只剩下一个子树分支，所以根节点（16）也向下移动了。所以删除关键字7后的结果如下：B+树经典面试题InnoDB中B+树可以存储多少行数据？为什么索引结构默认使用B+树而不是hash、二叉树、红黑树、B-tree？B-树和B+树的区别InnoDB中的B+树可以存储多少行数据？这个问题的简单答案是：大约2000万行。在计算机中，磁盘存储数据的最小单位是扇区，一个扇区的大小为512字节。在文件系统中，最小的单位是块，一个块的大小为4k；InnoDB存储引擎的最小存储单元是页，页的大小为16k。因为B+树的叶子存储数据，内部节点存储键值+指针。索引组织表通过非叶子节点和指针的二分查找方式确定数据在哪个页，然后在数据页中找到需要的数据；假设B+树的高度为2，有一个根节点和若干个叶子节点。这棵B+树存储的记录总数=根节点指针数*单个叶节点记录的行数。如果一行记录的数据大小为1k，那么单个叶子节点可以存储的记录数=16k/1k=16。非叶子节点存储了多少个指针？我们假设主键ID是bigint类型，长度为8字节，InnoDB源码中设置指针大小为6字节，所以是8+6=14字节，16k/14B=16*1024B/14B=1170。因此一棵高度为2的B+树可以存储1170*16=18720条这样的数据记录。同样，一棵高度为3的B+树可以存储1170*1170*16=21902400条，也就是说大约可以存储2000万条记录。B+树的高度一般为1-3层，已经满足了千万级的数据存储。为什么索引结构默认使用B+树而不是B-Tree、Hash散列、二叉树、红黑树？简单回答如下：Hash散列只适合等值查询，不适合范围查询。一般的二叉树可以特化为链表，相当于全表扫描。红黑树是一种特殊的平衡二叉树。当MySQL数据量很大时，索引的体积也会很大。如果内存无法存储，则从磁盘读取。还有很多次。B-Tree，叶子节点和非叶子节点都存储数据，同样的数据量，B+树更短更强，也就是说同样的数据量，B+树数据结构，磁盘查询次数会少点。B-tree和B+树的区别B-tree的内部节点存储数据；而B+树的内部节点不存储数据，只作为索引，其叶子节点存储数据。B+树的相邻叶子节点是通过链表指针连接起来的，而B-树则不是。在查找过程中，B-tree在找到具体值后结束，而B+树在结束前需要通过索引找到叶子节点中的数据。B-tree中的任何关键字出现并且只出现在一个节点中。B+树可以出现多次。参考并感谢B+树看这篇文章就够了[1]B-tree和B+树插入删除图解详解[2]InnoDB中B+树可以存储多少行数据？[3]本文转载自微信公众号“捡蜗牛的小男孩”，可通过以下二维码关注。转载请联系捡蜗牛的小男孩公众号。
