有二叉查找树为什么还要B树
数的高度
B树
- 查询
- 注意
B+树
B树和B+树的区别
- B+树相比B树的优势：
MongoDB
Mysql
- MySQL索引结构
- 所以二叉树就得变成多叉树，如m叉树，那么m多少合适？
- 索引有利也有弊，它会让写入数据的效率下降。这是为什么呢？
- B Tree索引在不同引擎中的差异
- 创建一个多列索引
- #">B Tree索引支持的查询类型#
- #">B Tree索引的限制#
总结

48 | B+树：MySQL数据库索引是如何实现的？
https://time.geekbang.org/column/article/77830

简单剖析B树（B-Tree）与Ｂ+树
https://blog.csdn.net/z_ryan/article/details/79685072

https://www.cnblogs.com/JasonCeng/p/12044109.html

有二叉查找树为什么还要B树

　　我们都知道二叉查找树的查找的时间复杂度是Ｏ(log N)，其查找效率已经足够高了，那为什么还有Ｂ树和Ｂ＋树的出现呢？难道它两的时间复杂度比二叉查找树还小吗？
　　答案当然不是，Ｂ树和Ｂ＋树的出现是因为另外一个问题，那就是磁盘ＩＯ；众所周知，ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。
　　所以，我们为了减少磁盘ＩＯ的次数，就必须降低树的深度，将“瘦高”的树变得“矮胖”。一个基本的想法就是：
　　每个节点存储多个元素，摒弃二叉树结构，采用多叉树

　　这样就引出来了一个新的查找树结构 ——多路查找树。根据AVL给我们的启发，一颗平衡多路查找树(B~树)自然可以使得数据的查找效率保证在O(logN)这样的对数级别上。

数的高度

叶子节点的高度为0，
图片.png

B树

B- 树就是 B 树，英文翻译都是 B-Tree，这里的“-”并不是相对 B+ 树中的“+”，而只是一个连接符。

B-树是一种自平衡的搜索树，形式很简单：
MySQL索引方式 B 树索引 - 图2
这就是一颗B树，特点如下：
（1）多路，非二叉树
（2）每个节点既保存索引，又保存数据
（3）搜索时相当于二分查找

查询

　　以上图为例：若查询的数值为26：
　　第一次磁盘ＩＯ：在内存中定位（50到100之间比较），比50少，在左子树；
　　第二次磁盘ＩＯ：在内存中定位（与25到40之间比较），在25到30范围内，左子树；
　　第三次磁盘ＩＯ：在内存中定位，找到26，终止。
整个过程中，我们可以看出：比较的次数并不比二叉查找树少，尤其是当某一节点中的数据很多时，但是磁盘IO的次数却是大大减少（一次磁盘io，查询出更多的数字进行比较）。比较是在内存中进行的，相比于磁盘IO的速度，比较的耗时几乎可以忽略。所以当树的高度足够低的话，就可以极大的提高效率。相比之下，节点中的元素多点也没关系，仅仅是多了几次内存交互而已，只要不超过磁盘页的大小即可。

注意

　　①、B树主要用于文件系统以及部分数据库索引，例如： MongoDB。而大部分关系数据库则使用B+树做索引，例如：mysql数据库；
　　②、从查找效率考虑一般要求B树的阶数m >= 3;
　　③、B-树上算法的执行时间主要由读、写磁盘的次数来决定，故一次I/O操作应读写尽可能多的信息。因此B-树的结点规模一般以一个磁盘页为单位。一个结点包含的关键字及其孩子个数取决于磁盘页的大小。

B+树

B+树是B树的变形树，非叶子节点只保存索引，不保存实际的数据，数据都保存在叶子节点中。有着比Ｂ树更高的查询效率
MySQL索引方式 B 树索引 - 图3
最核心的特点如下：
（1）多路非二叉
（2）只有叶子节点保存数据（B+树的数据都存储在叶子结点中，方便扫库，只需要扫一遍叶子结点即可。）
（3）搜索时相当于二分查找
（4）叶子节点增加了相邻节点的指向指针

B树和B+树的区别

　　Ｂ＋树的查找和Ｂ树一样，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。

　　（1）Ｂ＋树中间节点没有卫星数据（索引元素所指向的数据记录），只有索引，而Ｂ树每个结点中的每个关键字都有卫星数据；这就意味着同样的大小的磁盘页b+树可以容纳更多节点元素，在相同的数据量下，Ｂ＋树更加“矮胖”，ＩＯ操作更少
（2）Ｂ树的查找只需找到匹配元素即可，最好情况下查找到根节点，最坏情况下查找到叶子结点，所说性能很不稳定，而Ｂ＋树每次必须查找到叶子结点，性能稳定
（3）在范围查询方面，B+树的优势更加明显
　　B树的范围查找需要不断依赖中序遍历。首先二分查找到范围下限，在不断通过中序遍历，直到查找到范围的上限即可。整个过程比较耗时。
　　而B+树的范围查找则简单了许多。首先通过二分查找，找到范围下限，然后同过叶子结点的链表顺序遍历，直至找到上限即可，整个过程简单许多，效率也比较高。
例如：同样查找范围[3-11]，两者的查询过程如下：
　　B树的查找过程：

B+树的查找过程：

B+树相比B树的优势：

　　1.单一节点存储更多的元素，使得查询的IO次数更少；
　　2.所有查询都要查找到叶子节点，查询性能稳定；
　　3.所有叶子节点形成有序链表，便于范围查询。

MongoDB

MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql。
MongoDB 是文档型的数据库，是一种 nosql，它使用类 Json 格式保存数据。比如之前我们的表可能有用户表、订单表、购物篮表等等，还要建立他们之间的外键关联关系。但是类Json就不一样了。
MySQL索引方式 B 树索引 - 图6

Mysql

Mysql作为一个关系型数据库，数据的关联性是非常强的，区间访问是常见的一种情况，B+树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历。

MySQL索引结构

数据库索引所用到的数据结构叫作 B+ 树。它是通过二叉查找树演化过来的。
它通过存储在磁盘的多叉树结构，做到了时间、空间的平衡，既保证了执行效率，又节省了内存。

由于b+树索引结构是存储在磁盘中的，那么每个节点的读取（或者访问），都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。二叉树的高度太高，我们想要减少IO操作，就得降低树的高度。

所以二叉树就得变成多叉树，如m叉树，那么m多少合适？

不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。

索引有利也有弊，它会让写入数据的效率下降。这是为什么呢？

数据的写入过程，会涉及索引的更新，这是索引导致写入变慢的主要原因。

对于一个 B+ 树来说，节点数 m 是根据页的大小事先计算好的，也就是说，每个节点最多只能有 m 个子节点。在往数据库中写入数据的过程中，这样就有可能使索引中某些节点的子节点个数超过 m，这个节点的大小超过了一个页的大小，读取这样一个节点，就会导致多次磁盘 IO 操作。我们该如何解决这个问题呢？

我们只需要将这个节点分裂成两个节点。但是，节点分裂之后，其上层父节点的子节点个数就有可能超过 m 个。不过这也没关系，我们可以用同样的方法，将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。这个分裂过程，你可以结合着下面这个图一块看，会更容易理解（图中的 B+ 树是一个三叉树。我们限定叶子节点中，数据的个数超过 2 个就分裂节点；非叶子节点中，子节点的个数超过 3 个就分裂节点）。
MySQL索引方式 B 树索引 - 图7

正是因为要时刻保证 B+ 树索引是一个 m 叉树，所以，索引的存在会导致数据库写入的速度降低。实际上，不光写入数据会变慢，删除数据也会变慢
我们可以设置一个阈值。在 B+ 树中，这个阈值等于 m/2。如果某个节点的子节点个数小于 m/2，我们就将它跟相邻的兄弟节点合并。不过，合并之后节点的子节点个数有可能会超过 m。针对这种情况，我们可以借助插入数据时候的处理方法，再分裂节点。

B Tree索引在不同引擎中的差异

	MyISAM	InnoDB
存储方式	前缀压缩技术	按照原数据格式
引用方式	通过数据的物理位置引用被索引的行	根据主键引用被索引的行

创建一个多列索引

CREATE TABLE People (
      last_name    varchar(50)        not null,
      first_name   varchar(50)        not null,
      dob          date             not null,
      gender       enum(‘m’,‘f’)    not null,
      key(last_name,first_name,dob) 普通索引
);

   索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时列的顺序。<br />

B Tree索引支持的查询类型#

   MySQL的B Tree索引适用于全键值、键值范围或键前缀查找，其中键前缀查找只适用于根据最左前缀的查找。前面所述的索引可细分为如下几种类型。<br />**     （1）全值匹配**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#1341899953)<br />       全值匹配指的是和索引中的所有列进行匹配。<br />       例如上面的People表的索引（last_name,first_name,dob）可以用于查找last_name=’Zeng’,first_name=’Chuang’,dob=’1996-01-01’的人。这就是使用了索引中的所有列进行匹配，即全值匹配。<br />**     （2）匹配最左前缀**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#1327934892)<br />       可以只使用索引的第一个列进行匹配。<br />       例如可以用于查找last_name=’Zeng’的人，即用于查找姓为Zeng的人，这里只使用了索引的最左列进行匹配，即匹配最左前缀。<br />**     （3）匹配列前缀**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#2492064254)<br />       可以只匹配某一列的值的开头部分。<br />       例如可以用于查找last_name LIKE ‘Z%’的人，即用于查找所有以Z开头的姓的人，这里只使用了索引最左列的前缀进行匹配，即匹配列前缀。<br />**     （4）匹配范围值**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#1680876385)<br />       可以只适用索引的第一列查找符合某个范围内的数据。<br />       例如可以用于查找last_name BETWEEN ‘Qiu’ AND ‘Zeng’的人，即用于查找姓在Qiu和Zeng之间的人，这里只使用了索引最左列的前缀进行范围匹配，即匹配范围值。<br />**     （5）精确匹配某一列并范围匹配另外一列**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#359171365)<br />       可以使第一列全匹配，第二列范围匹配。<br />       例如可以用于查找last_name=’Zeng’ AND first_name LIKE ’C%’的人，即用于查找姓是Zeng，名字以C开头的人，这里使用了索引的最左列精确匹配，第二列进行范围匹配，即精确匹配某一列并范围匹配另外一列。<br />**     （6）只访问索引的查询**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#2710183965)<br />       查询只需访问索引，而无须访问数据行。<br />       例如select last_name, first_name where last_name=’Zeng’; 这里只查询索引所包含的last_name和first_name列，则无须读取数据行。<br />

B Tree索引的限制#

   根据上面介绍的B Tree索引支持的查询类型，我们可以知道，它同样会存在一些限制。<br />**     （1）只能按照索引的最左列开始查找。**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#886805366)<br />       例如People表中的索引无法用于查找first_name为’Chuang’的人，也无法查找某个特定生日的人，因为这两个列都不是最左数据列。<br />**     （2）只能按照索引最左列的最左前缀进行匹配。**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#138548883)<br />       例如People表中的索引无法查找last_name LIKE ‘%eng’的人，虽然last_name就是此索引的最左列，但MySQL索引无法查找以‘eng’结尾的last_name的记录。<br />**     （3）只能按照索引定义的顺序从左到右进行匹配，不能跳过索引中的列。**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#3258380873)<br />       例如People表中的索引无法用于查找last_name=’Zeng’ AND bod=’1996-01-01’的人，因为MySQL无法跳过索引中的某一列而使用索引中最左列和排在末尾的列进行组合。如果不指定索引中中间的列，则MySQL只能使用索引的最左列，即第一列。<br />**     （4）如果查询中有某个列的范围查询/模糊查询，则其右边所有列都无法使用索引优化查找。**[**#**](https://www.cnblogs.com/JasonCeng/p/12044109.html#2015938387)<br />       例如有这样一个查询：where last_name=’Zeng’ AND first_name LIKE ’C%’ AND dob=’1996-01-01’; 这个查询只能使用索引的前两列，因为这里LIKE是一个范围条件，则first_name后面的索引列都将失效。（优化点：尽量不要在索引列中使用LIKE等范围条件，改用多个等于条件来替代，保证后面的索引列能生效。）<br />       <br />阅读到这里，我们应该明白了索引列的顺序是多么的重要，上面的这些限制都和索引列的顺序有关。在性能优化时，可能需要使用相同的列但顺序不同的索引来满足不同类型的查询需求。

总结

本文由简悦 SimpRead 转码，原文地址 blog.csdn.net

1. 谈谈对索引的理解

索引是存储引擎用于提高数据查询效率的一种数据结构，索引类似于字典里的目录。Mysql 中的索引是在存储引擎层实现的，索引的数据结构和存储引擎有关，在 MySQL 中使用较多的索引有 Hash 索引、B 树索引和 B+ 树索引。
- hash 索引：底层就是 hash 表。进行查找时，根据 key 调用 hash 函数获得对应的 hashcode，根据 hashcode 找到对应的数据行地址，根据地址拿到对应的数据。
- B 树索引：B 树是一种多路搜索树，n 路搜索树代表每个节点最多有 n 个子节点。每个节点存储 key + 指向下一层节点的指针 + 指向 key 数据记录的地址。查找时，从根结点向下进行查找，直到找到对应的 key。
- B + 树索引：B + 树是 b 树的变种，主要区别在于：B + 树的非叶子节点只存储 key + 指向下一层节点的指针，也就是只存索引，不存数据，数据都保存在叶子节点中。另外，B + 树的叶子节点之间通过指针来连接，构成一个有序链表，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。
索引有三个优点： ①减少了服务器需要扫描的数据量；②帮助服务器避免排序；③将随机 IO 变为顺序 IO，因为 B+ 树索引是有序的，它将相邻的数据都存储在一起。
索引的缺点：创建索引和维护索引会耗费时间；索引会占用物理空间；当对表进行增删改时，索引也需要动态维护，这样会降低数据的维护速度。一般在频繁使用或需要排序的字段上建立索引，而对于很少查询或重复值较多的列，不适合建立索引。、、

（InnoDB 中使用了 B+ 树索引，它先通过 B+ 树找到数据所在的页，然后将页读到内存，在内存中找到要查找的数据。Mysql 将索引存放在磁盘而不是内存中，减少了内存消耗）

2. B 树和 B + 树的区别？为什么使用 B + 树？（B + 树底层文件是怎么存储的）

B + 树的中间节点存的是索引，不存储数据，数据都保存在叶子节点中，而 B 树的所有节点都能存放数据。所以 B + 树磁盘读写的代价比 B 树低，因为中间节点不放数据，所以相同的磁盘块能存放更多的节点，一次性读入内存的节点数量也就越多，所以 IO 读写次数就降低了。
B + 树的叶子节点位于同一层，数据也都位于叶子节点中，所以每次查找都是从根节点找到叶子节点，效率很稳定。而 B 树在查到关键字后就停止查找了，效率不够稳定。
B + 树的叶子节点还按照大小，通过链表有序的串联在一起，在进行遍历查询时，只需要遍历这个链表即可，而且还支持范围查询，查到范围的开始节点，然后往后遍历即可实现。而 B 树没有这样的链表，只能通过中序遍历来查找数据，不支持范围查询。

3. MySQL 为什么要用 B + 树存储索引？而不用平衡二叉树（红黑树）、Hash 索引 (散列表)、B 树、跳表？

Hash 索引 (散列表)：如果只查询单个值的话，hash 索引的效率非常高，时间复杂度为 O(1)。但是 hash 索引有几个问题：
- 1）不支持范围查询；
- 2）不支持索引值的排序操作；
- 3）不支持联合索引的最左匹配规则。
平衡二叉树（红黑树）：查询性能也好，时间复杂度 O(logn)，中序遍历可以得到一个从小到大有序的数据序列，但不支持区间查找。而且由于是二叉树，当数据量很大时树的层数就会很高，从树的根结点向下寻找的过程，每读 1 个节点，都相当于一次 IO 操作，因此他的 I/O 操作会比 B + 树多的多。
B 树索引：见上面 B 树和 B + 树的区别↑。
跳表：是一种链表加多层索引的结构，时间复杂度 O(logn)，支持区间查找，而 B + 树是一种多叉树，可以让每个节点大小等于操作系统每次读取页的大小，从而使读取节点时只需要进行一次 IO 即可。而且同数量级的数据，跳表索引的高度会比 B+ 树的高，导致 IO 读取次数多，影响查询性能。

4. B + 树一个节点有多大？一千万条数据，B + 树多高？

B + 树一个节点的大小设为一页或页的倍数最为合适。因为如果一个节点的大小 < 1 页，那么读取这个节点的时候其实读取的还是一页，这样就造成了资源的浪费。
（一个中文是3个字节，英文1个字节；字节=Byte，1Byte=8bit，1KB=1024Byte）
在 MySQL 中 B+ 树的一个节点大小为 “1 页”，Innodb的数据页一页默认是16K。之所以设置为一页，是因为对于大部分业务，一页就足够了：
- 首先 InnoDB 的 B + 树中，非叶子节点存的是 key + 指针；叶子节点存的是数据行。
- 如通过主键构建的b+树
  - 对于非叶子节点，如果 key 使用的是 int，则为 4 字节，指针在 mysql 中为 6 字节，一共是 10 字节，则 16k 能存放 16 * 1024 / 10 = 1638 个索引指针。所以一次可以加载1638个数据到内存中，进行搜索比较；也就是一次io操作，会有 1638 条数据；
  - 对于叶子节点，存放的是数据，如果一行数据大小为 1k（约为333个中文，主键构建的b+树是聚簇索引，叶子节点为全部数据），那么一页就能存 16 条数据；
- 于是可以算出：
- 对于一颗高度为 1 的 B + 树，根节点存储索引指针节点，那么它有 1600 个根节点。
- 每个叶子节点可以存储 16 条数据，一共1600 x 16 = 25600 条数据。
- 根节点的步长为16：
- 对于高度为 2 的 B + 树，就可以存放 1600x 1600x 16 = 4千多万条数据，通过主键查询只需要 3 次 IO 操作就能查到对应数据。
- 对于高度为 3 的 B + 树，就可以存放 1600 x 1600 x 1600 X 16 =700多亿条数据，通过主键查询只需要 4 次 IO 操作就能查到对应数据。
- 所以在 InnoDB 中， B + 树高度一般为 2 层时，就能满足千万级的数据存储，
- 在实际过程中，mysql会动态调整b+的结构，让其尽量保持平衡，如上面的这种情况，3层能存储700多亿条数据，但是并不是第三层都存储满了，也无需每次都加载正好一页，也可动态调整，比如加载200页。

如通过普通索引构建的b+树
- 对于非叶子节点，如果key为varchar类型，设置为32个字节的长度，指针占用6字节；则 16k 能存放 16 * 1024 / 38 = 431个索引指针。
- 对于叶子节点，存放的数当前key的值和主键值，主键为int类型占用4个字节，一行数据共36个字节，那么一页就能存 113 条数据：16 * 1024 / 36 = 455