b与b+树区别_b树和二叉树区别

二三树、B树(多路平衡查找树)、B+树 　　二三树介绍(2-3树的理解对红黑树和B类树的理解大有帮助) 　　1、满足二分搜索树的基本性质2、结点可以存放一个素或两个素，对于存放一个素的节点，和二分搜索树一样，左小右大；对于存放两个素的结点，左小中中右大，即左子树存放比它们都小的素，右子树存放比它们都大的素，中间结点存放在他们中间的素。3、2-3树是绝对平衡的二分搜索树(从根节点到任意一个叶子结点所经过的结点一定是相同的)，这种性质和在构建2-3树时的方法有关。

图1 　　为了维护2-3树绝对平衡的性质，在构建树，也就是插入结点时就要符合一定的逻辑。如下： 　　1、添加结点不能添加到空位置，除非此时整个树为空。 　　2、如果按照二分搜索树的方式插入素，当前插入位置是空，根据上一条，不能插入，此时可以放在最后一个叶子结点上。 　　上面的规则很空洞，下面看一个具体的例子： 　　示例： 　　如图2在插入42结点时，此时为空，直接插入在根节点位置。 　　如图2所示，在插入37时，按照二分搜索树，应该插在42 的左孩子上，但此时为空，不能插入，此时树中只有42一个结点，则37和42放一起。结果如图3所示。

图2

图3 　　如图3所示，如果此时再往树中添加素12，按照二分搜索树的规则和2-3树的规则，应该插入在37的左孩子上，但此时为空，不能插入。所以放在最后一个叶子结点上，即根节点上，和37,42挤一挤。如图4所示：

图4 　　但2-3树不允许有这样的节点(只能包含一个或两个素)，所以对图4继续调整，如图5所示：

图5 　　如果此时再添加18素，按理说应该放在12的右子树上，但12的右子树为空，不能放，所以先委屈18素和12素挤一挤，如图6所示。

图6 　　如果此时再往树中添加6素，按理说应该放在12的左子树上，但此时12的左子树为空，不能放。所以也委屈他和12 、18挤一挤，就像图4那样，结果如图7所示，

图7 　　但图7不是绝对平衡的，因为从根节点到42经过的结点和到6所经过的结点是不同的。该怎么办呢？ 　　答：12结点和它的父节点结合，就是让他们挤一挤，变成图8。

图8 　　如果此时要插入11呢？按照上面的规则，应该和6挤一挤，变成图9：

图9 　　如果此时再添加5素呢？应该和5、6、11挤一挤，如图10

图10 　　此时不满足2-3树要求，对其调整，如图11

图11 　　此时不满足绝对平衡的条件，把6和12、37挤一挤，变成图12

图12 　　此时不满足要求，变成图13

图13 　　—————————分割线———————— 　　上面的多个图展示了往2-3树中添加素的处理过程，整个过程始终保持绝对平衡。注意添加素的先后顺序是42->37->18->12->11->6->5，如果按照二分搜索树的添加规则，是不是会严重偏斜啊，所以二三树可以避免这种严重失衡。 　　总的原则如下：



　　—————————————-分割线—————————————- 　　B树，又称多路平衡查找树，B数中所有结点的孩子个数的最大值称为B树的阶，用m表示。一颗m阶B树是一颗空树或者是符合一系列条件的m叉树。 　　性质1：m阶B树，每个节点最多有m叉，那么该节点最多有m-1个关键字(素) 　　树中每个结点最多有m棵子树，最多有m-1个关键字。

性质1 　　性质2:除根节点外，其它非叶子节点至少有(m/2的结果并向上取整）个孩子节点，也就是至少有 　　(m/2的结果并向上取整减1）个关键字。

性质2 　　性质3:若根节点不是叶子节点，则根节点至少有两个孩子节点。即根节点最少有1个关键字。

　　性质4:每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。

　　性质5:所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。

　　综上，根节点的关键字数量范围：，非根节点的关键字数量范围：m/2的结果并向上取整减一。 　　比如这里有一个5阶的B树，根节点数量范围：1 <= k <= 4，非根节点数量范围：2 <= k <= 4。因为5/2=2.5,向上取整为3，再减一为2。 　　2-3树是特殊的B树，3阶B树(3阶意味着最多只能有2个关键字(素)) 　　B数性质总结如下：

　　————————————–B+树———————————————–

　　性质1:m阶B+树的每个分支节点最多有m棵子树(与B树相同)

这里m=3吧 　　性质2：根节点要么没有子树，要么至少有两个子树(与B树相同)

　　性质3：除根节点外，其它每个分支节点至少有m/2(向上取整)棵子树(与B树略相同，但B+树n个关键字对应n个子树)

　　性质4：有n棵子树的节点恰好有n个关键字(B树是有n-1个关键字才有n个节点)

　　性质5：所有叶子结点包含全部关键字及指向对应记录的指针，而且叶子结点按关键字大小顺序链接。并将所有叶子结点链接起来。

　　性质6：所有分支结点(可看成是索引的索引）中仅包含它的各个子结点(即下级索引的索引块）中最大关键字及指向子结点的指针。

　　B+树性质总结

　　B+树案例

　　面试题:B树和B+树的区别？

　　(1)B树每个节点既有key又有数据，B+树的非叶子结点只有key(一行记录的主键id)，没有数据(所谓数据，就是该行记录所在的地址)。 　　(2)B树的叶子结点之间是没有关系的，而B+树的叶子结点是相互连接的，类似链表，而且是双向的链表。 　　(3)在查找数据时，对于B树来讲，不一定非要找到叶子结点，而对于B+树来讲，是一定要找到叶子结点的。因为B+树的数据都在叶子结点，非叶子结点是没有数据的。 　　延伸: 　　B树特点:(1)每一层的节点是排好序的。(2)一个节点可以存储多个素，多个素之间也是按序排列的。 　　B+树特点:(1)B树的多有特点(2)叶子节点之间有指针(3)非叶子节点上的素在叶子节点上都冗余了，也就是叶子节点存储了所有的素，并且排好序。 　　面试题:为何mysql用B+树作为索引的存储形式？ 　　用B+树就是因为B+树层级低，一般三层就能容纳千万级别的数据，而千万数据，跳表层级高，检索的话IO次数多。据说是因为每层有很多个分叉。 　　因为B树的每个节点都有key和数据，而B+树的非叶子节点是没有数据的，所以相同的大小，B+树能存储更多的数据。 　　因为B+树叶子节点有指针，所以对于范围查找更方便。 　　先解释为何其它数据结构不合适？ 　　(0) hash:hash值是无序的，hash结构不支持范围查找，还存在hash冲突，多个key对应的哈希值相同，需要逐个对比。 　　(1)二分查找树:如果数据有序排列，会退化成链表，时间复杂度为O(n) 　　(2)平衡二叉树(AVL树，本身也是二分搜索树)：树越高，查找越慢，而AVL容易变得越来越高。另外，对于范围查找，如下图查找大于等于5的数，需要三次定位到5，然后多次回查，效率较低。

　　(4)B树:插入相同量的数据，B树的高度比AVL树低，所以查找效率相对较高，因为AVL树每个节点最多只有两个子节点，而B数则可以有多个子节点，所以每层能存储的节点多，可以降低层数。

　　但B树仍然存储回旋查找慢的问题，如上图，查找大于5的素，需要先定位到5，然后往回查。 　　(5)最终选择了B+树

　　如上图所示，在B树的基础上增加了叶子节点的链接，且它们之间是排好序的，形成了双向链表，这样就可以很容易的某个范围的数据，而不用回查。 　　当SQL语句中有order by时，如果order by后的字段是索引字段，就可以提升效率，因为本来就排好序了。 　　索引：Innodb & Myisam 　　



　　聚簇索引和非聚簇索引

　　下面是两种索引的展示：

　　基于聚簇索引可以引申出很多索引，左边是主键索引(以主键值作为B+树节点)，右边是辅助索引(非主键索引)，因为聚簇索引中数据和索引值存在一起，可以通过索引直接查找到值，比如查找id为30的记录，可以在左边的主键索引中直接查到；但如果用的辅助索引，只可以查找到该行的主键id，需要再次查找左边的主键索引才能查到全部数据。 　　主键索引是聚簇索引的默认实现。如果没有主键，就会选择一个唯一且非空的字段构建索引来代替(唯一非空索引)，如果没有这样的字段，就会生成一个隐式的聚簇索引。 　　索引覆盖:如果查的是主键，可以通过辅助索引直接查到 　　回表:如果查age字段，需要多走一次索引，先查找到id，再查到记录,需要查两次 　　索引下推: 　　非聚簇索引：根据主键查找到该行记录的地址

　　索引的扩展： 　　单列索引 与 复合索引 　　只包含一个字段的索引叫做单列索引，包含两个或以上字段的索引叫做复合索引（或组合索引）。建立复合索引时，字段的顺序极其重要。 　　下面这个SQL语句在 列X，列Y，列Z 上建立了一个复合索引。 　　其实这相当于建立了三个索引，分别是： 　　1、单列索引（列X） 2、复合索引（列X, 列Y） 3、复合索引（列X，列Y，列Z）。 　　索引失效 　　

　　索引失效一般出现在联合索引中，a和b是两个字段，(2,4)是(a,b)字段的值，对于这种联合索引，a字段的值整体是有序的，而b字段的值整体是无序的，但对于相同的a字段来讲，对应的b字段的值也是有序的。 　　比如要查找a大于1，且b大于1的数据，如下图，可以很快的定位到a大于1的位置，但由于b是无序的，所以还是需要从(2,1)往后逐个遍历。

　　但如果是查找a=2，b=1就可以通过索引方便查找，因为可以通过索引快速找到a=1,又因为相同的a对应的b也是有序的，所以方便查找到b=1。 　　索引失效案例： 　　创建联合索引，把phone和lan_id字段搞成联合索引explain select * from user where phone=’1212′ and lan_id=1; — 索引正常explain select * from user where lan_id=1; — 索引失效explain select * from user where phone>’1212′ and lan_id=1; — 索引失效explain select * from user where phone like ‘1212%’; — 有效explain select * from user order by phone; — 有效