B+树

一、B-树1. B-树是一种多路搜寻树（并不一定是二叉的） 1970年，R.Bayer和E.mccreight提出了一种实用于外查找的树，它是一种均衡的多叉树，称为B树（或B-树、B_树）。 2. 一棵m阶B树(balanced tree of order m)是一棵均衡的m路搜寻树。它或者是空树，或者是满足下列性质的树： 根结点至多有两个子女；每个非根节点所蕴含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；除根结点以外的所有结点（不包含叶子结点）的度数正好是关键字总数加1，故外部子树个数 k 满足：┌m/2┐ <= k <= m ；所有的叶子结点都位于同一层。二、特点：是一种多路搜寻树（并不是二叉的）： 定义任意非叶子结点最多只有M个儿子；且M>2；根结点的儿子数为[2, M]；除根结点以外的非叶子结点的儿子数为[M/2, M]；每个结点寄存至多M/2-1（取上整）和至少M-1个关键字；（至多2个关键字）非叶子结点的关键字个数=指向儿子的指针个数-1；非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；所有叶子结点位于同一层；如：（M=3） B-树的搜寻，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果 命中则完结，否则进入查问关键字所属范畴的儿子结点；反复，直到所对应的儿子指针为 空，或曾经是叶子结点； 三、B-树的个性：关键字汇合散布在整颗树中；任何一个关键字呈现且只呈现在一个结点中；搜寻有可能在非叶子结点完结；其搜寻性能等价于在关键字选集内做一次二分查找；主动档次管制；四、B+树B+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一棵B+树蕴含根节点、外部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个蕴含两个或两个以上孩子节点的节点。 五、用处：B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在应用B+树作为元数据索引。B+ 树的特点是可能保持数据稳固有序，其插入与批改领有较稳固的对数工夫复杂度。B+ 树元素自底向上插入。 六、B+树的定义1. B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差别在于： 有n棵子树的结点中含有n个关键字，每个关键字不保留数据，只用来索引，所有数据都保留在叶子节点。所有的叶子结点中蕴含了全副关键字的信息，及指向含这些关键字记录的指针，且叶子结点自身依关键字的大小自小而大程序链接。所有的非终端结点能够看成是索引局部，结点中仅含其子树（根结点）中的最大（或最小）关键字。通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。2. B+树是B-树的变体，也是一种多路搜寻树： 其定义根本与B-树同，除了：非叶子结点的子树指针与关键字个数雷同；非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；为所有叶子结点减少一个链指针；所有关键字都在叶子结点呈现；如：（M=3） B+的搜寻与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树能够在 非叶子结点命中），其性能也等价于在关键字选集做一次二分查找； 七、B+的个性：所有关键字都呈现在叶子结点的链表中（浓密索引），且链表中的关键字恰好是有序的；不可能在非叶子结点命中；非叶子结点相当于是叶子结点的索引（稠密索引），叶子结点相当于是存储（关键字）数据的数据层；更适宜文件索引零碎；八、B*树：1. 是B+树的变体，在B+树的非根和非叶子结点再减少指向兄弟的指针； ...

B树与B+树的区别有两个：1、B树的非叶子节点是存储数据的，而B+树的非叶子节点只存储索引信息2、B+树的非最右侧的叶子节点向右会指向右侧的叶子节点，造成一个有序的连表 在查找数据的时候，B树须要依据数据是比拟查找查问次数比拟多，因为B+树存储的是数据的索引，所以只有一次IO就能够查找到数据而且B+树非叶子节点只存储索引，所以能存储更多的索引，使树的高度升高

最艰难的事件就是意识本人！集体网站，欢送拜访！ 前言：本篇文章次要是论述下 联结索引 在 B+Tree 上的理论存储构造。本文次要解说的内容有： 联结索引在B+树上的存储构造联结索引的查找形式为什么会有最左前缀匹配准则在分享这篇文章之前，我在网上查了对于MySQL联结索引在B+树上的存储构造这个问题，翻阅了很多博客和技术文章，其中有几篇讲述的与事实相悖。具体如下：很多博客中都是说：联结索引在B+树上的 非叶子节点 中只会存储 联结索引 中的第一个索引字段 的值，联结索引的其余索引字段的值只会呈现在 B+树 的 叶子节点 中 。（其实这句话是不对的） 如下图，就是 谬误的 联结索引的 B+树 存储结构图： 庆幸的是通过一直查问发现有一条是来自思否社区的对于【联结索引 在 B+Tree 上的存储构造？】问答，有答主答复了这个问题，并贴出了一篇文章和一张图以及一句简略的形容。PS：贴出的文章链接曾经打不开了。所以在这样的条件下本篇文章就诞生了。 联结索引存储构造：上面就援用思否社区的这个问答来开展咱们明天要探讨的联结索引的存储构造的问题。来自思否的发问，联结索引的存储构造(https://segmentfault.com/q/10...有码友答复如下： 联结索引 bcd , 在索引树中的样子如下图 ， 在比拟的过程中 ，先判断 b 再判断 c 而后是 d ： 因为答复只有这么一张图一句话，可能会让大家有点看不懂，所以咱们就借助前人的肩膀用这个例子来更加粗疏的讲探寻一下联结索引在B+树上的存储构造吧。 首先，有一个T1表， 而后表T1有字段a,b,c,d,e，其中a是主键，除e为varchar其余为int类型，并创立了一个联结索引idx_t1_bcd(b,c,d)，而后b、c、d三列作为联结索引，在B+树上的构造正如上图所示。联结索引的所有索引列都呈现在索引数上，并顺次比拟三列的大小。上图树高只有两层不容易了解，上面是假如的表数据以及我对其联结索引在B+树上的结构图的改良。 PS：基于InnoDB存储引擎。 index（b、c、d）联结索引在B+树上的结构图如下： T1表中的数据如下图：（ 上图 B+树 中的数据就来自下图 ） 通过这俩图咱们心里对联结索引在B+树上的存储构造就有了个大略的意识。上面用我的语言为大家解释一下吧。咱们先看T1表，他的主键暂且咱们将它设为整型自增的 ，InnoDB会应用主键索引在B+树保护索引和数据文件，而后咱们创立了一个联结索引（b，c，d）也会生成一个索引树，同样是B+树的构造，只不过它的 data局部 存储的是联结索引所在行记录的主键值 （上图叶子节点紫色背景局部） 。为什么是 主键值，而不是 整个行记录呢？ 因为这个 联结索引 是个 非聚簇索引 。 好了大抵状况都介绍完了。上面咱们联合这俩图来解释一下。 ...

我们已经讲过了MySQL InnoDB索引原理和算法，这里来说下如何管理和使用B+树索引以及一些新的特性。 B+ 树索引的管理我们在InnoDB引擎中常用的索引基本都是B+ 树索引。 创建和删除索引它的创建和删除有两种方法： # 方式一：alter table, 此时index和key均可以，如果要求所有值均不重复，加上uniquealter table tbl_name add [unique] index|key index_name (index_col_name,...);alter table tbl_name drop index|key index_name;# 方式二：create/drop index, 此时只能用indexcreate index index_name on tbl_name (index_col_name,...);drop index index_name on tbl_name;修改索引MySQL没有提供修改索引的命令，我们一般先删掉索引，再重建同名索引达到修改的目标。 查看索引我们在查看数据表描述时可以看到都有哪些索引，有三种方法： # 方法一：查看创建表的语句mysql> show create table serviceHost;| Table | Create Table | t | CREATE TABLE `t` ( `id` int(11) NOT NULL AUTO_INCREMENT, `a` varchar(20) DEFAULT NULL, `b` varchar(20) DEFAULT NULL, `c` varchar(20) DEFAULT NULL, `d` varchar(20) DEFAULT NULL, `e` varchar(20) DEFAULT NULL, `f` varchar(20) DEFAULT NULL, PRIMARY KEY (`id`), UNIQUE KEY `a` (`a`), KEY `idx_b` (`b`), KEY `idex_cde` (`c`,`d`,`e`)) ENGINE=InnoDB DEFAULT CHARSET=utf8 |1 row in set (0.00 sec)可以看到该表中有4个索引，主键集合索引(id)，唯一辅助索引(a)，单列辅助索引(b)，组合辅助索引(c,d,e)。 ...

也许你经常用MySQL，也会经常用索引，但是对索引的原理和高级功能却并不知道，我们在这里一起学习下。 InnoDB存储索引在数据库中，如果索引太多，应用程序的性能可能会受到影响；如果索引太少，又会对查询性能产生影响。所以，我们要追求两者的一个平衡点，足够多的索引带来查询性能提高，又不因为索引过多导致修改数据等操作时负载过高。 InnoDB支持3种常见索引： 哈希索引B+ 树索引全文索引我们接下来要详细讲解的就是B+ 树索引和全文索引。 哈希索引InnoDB存储引擎支持的哈希索引是自适应的，会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。这块内容我们先不展开说，后续补充。 B+ 树索引B+ 树索引是目前关系型数据库系统中查找最为常用和有效的索引，其构造类似于二叉树，根据键值对快速找到数据。B+ 树（balance+ tree）由B树（banlance tree 平衡二叉树）和索引顺序访问方法（ISAM: Index Sequence Access Method）演化而来，这几个都是经典的数据结构。而MyISAM引擎最初也是参考ISAM数据结构设计的。 基础数据结构想要了解B+ 树数据结构，我们先了解一些基础的知识。 二分查找法又称为折半查找法，指的是将数据顺序排列，通过每次和中间值比较，跳跃式查找，每次缩减一半的范围，快速找到目标的算法。其算法复杂度为log2(n)，比顺序查找要快上一些。 如图所示，从有序列表中查找48，只需要3步： 详细的算法可以参考二分查找算法。 二叉查找树二叉查找树的定义是在一个二叉树中，左子树的值总是小于根键值，根键值总是小于右子树的值。在我们查找时，每次都从根开始查找，根据比较的结果来判断继续查找左子树还是右子树。其查找的方法非常类似于二分查找法。 平衡二叉树二叉查找树的定义非常宽泛，可以任意构造，但是在极端情况下查询的效率和顺序查找一样，如只有左子树的二叉查找树。 若想构造一个性能最大的二叉查找树，就需要该树是平衡的，即平衡二叉树（由于其发明者为G. M. Adelson-Velsky 和 Evgenii Landis，又被称为AVL树）。其定义为必须满足任何节点的两个子树的高度最大差为1的二叉查找树。平衡二叉树相对结构较优，而最好的性能需要建立一个最优二叉树，但由于维护该树代价高，因此一般平衡二叉树即可。 平衡二叉树查询速度很快，但在树发生变更时，需要通过一次或多次左旋和右旋来达到树新的平衡。这里不发散讲。 B+ 树了解了基础的数据结构后，我们来看下B+ 树的实现，其定义十分复杂，目标是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在该树中，所有的记录都按键值的大小放在同一层的叶子节点上，各叶子节点之间有指针进行连接（非连续存储），形成一个双向链表。索引节点按照平衡树的方式构造，并存在指针指向具体的叶子节点，进行快速查找。 下面的B+ 树为数据较少时，此时高度为2，每页固定存放4条记录，扇出固定为5（图上灰色部分）。叶子节点存放多条数据，是为了降低树的高度，进行快速查找。 当我们插入28、70、95 3条数据后，B+ 树由于数据满了，需要进行页的拆分。此时高度变为3，每页依然是4条记录，双向链表未画出但是依然是存在的，现在可以看出来是一个平衡二叉树的雏形了。 InnoDB的B+ 树索引InnoDB的B+ 树索引的特点是高扇出性，因此一般树的高度为2~4层，这样我们在查找一条记录时只用I/O 2~4次。当前机械硬盘每秒至少100次I/O/s，因此查询时间只需0.02~0.04s。 数据库中的B+ 树索引分为聚集索引（clustered index）和辅助索引（secondary index）。它们的区别是叶子节点存放的是否为一整行的完整数据。 聚集索引聚集索引就是按照每张表的主键（唯一）构造一棵B+ 树，同时叶子节点存放整行的完整数据，因此将叶子节点称为数据页。由于定义了数据的逻辑顺序，聚集索引也能快速的进行范围类型的查询。 聚集索引的叶子节点按照逻辑顺序连续存储，叶子节点内部物理上连续存储，作为最小单元，叶子节点间通过双向指针连接，物理存储上不连续，逻辑存储上连续。 聚集索引能够针对主键进行快速的排序查找和范围查找，由于是双向链表，因此在逆序查找时也非常快。 我们可以通过explain命令来分析MySQL数据库的执行计划： # 查看表的定义，可以看到id为主键，name为普通列mysql> show create table dimensionsConf;| Table | Create Table | dimensionsConf | CREATE TABLE `dimensionsConf` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(20) DEFAULT NULL, `remark` varchar(1024) NOT NULL, PRIMARY KEY (`id`), FULLTEXT KEY `fullindex_remark` (`remark`)) ENGINE=InnoDB AUTO_INCREMENT=178 DEFAULT CHARSET=utf8 |1 row in set (0.00 sec)# 先测试一个非主键的name属性排序并查找，可以看到没有使用到任何索引，且需要filesort（文件排序），这里的rows为输出行数的预估值mysql> explain select * from dimensionsConf order by name limit 10\G;*************************** 1. row *************************** id: 1 select_type: SIMPLE table: dimensionsConf type: ALLpossible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 57 Extra: Using filesort1 row in set (0.00 sec)# 再测试主键id的排序并查找，此时使用主键索引，在执行计划中没有了filesort操作，这就是聚集索引带来的优化mysql> explain select * from dimensionsConf order by id limit 10\G;*************************** 1. row *************************** id: 1 select_type: SIMPLE table: dimensionsConf type: indexpossible_keys: NULL key: PRIMARY key_len: 4 ref: NULL rows: 10 Extra: NULL1 row in set (0.00 sec)# 再查找根据主键id的范围查找，此时直接根据叶子节点的上层节点就可以快速得到范围，然后读取数据mysql> explain select * from dimensionsConf where id>10 and id<10000\G;*************************** 1. row *************************** id: 1 select_type: SIMPLE table: dimensionsConf type: rangepossible_keys: PRIMARY key: PRIMARY key_len: 4 ref: NULL rows: 56 Extra: Using where1 row in set (0.00 sec)辅助索引辅助索引又称非聚集索引，其叶子节点不包含行记录的全部数据，而是包含一个书签（bookmark），该书签指向对应行数据的聚集索引，告诉InnoDB存储引擎去哪里查找具体的行数据。辅助索引与聚集索引的关系就是结构相似、独立存在，但辅助索引查找非索引数据需要依赖于聚集索引来查找。 ...