数据库索引采用B树和B+树的原因

1.数据文件存储的方式

数据库文件存储都是以磁盘文件存储在系统中的，这也是数据库能持久化存储数据的原因

2.从数据库读取数据的原理

从数据库读取数据，先暂且不考虑从缓存中读取数据的情况，那就是从磁盘文件中读取数据的，我们知道从磁盘文件中读取数据是比较耗时的，数据库的select操作时间，取决于执行磁盘IO的次数，因此尽量减少IO就可以显著提升数据的查询速度

3.减少磁盘IO操作的影响因素

3.1：磁盘io与预读

   磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘IO的时间，大概9ms左右。这个成本是访问内存的十万倍左右；正是由于磁盘IO是非常昂贵的操作，所以计算机操作系统对此做了优化：预读；每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中。因为局部预读原理说明：当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页（page）。一页的大小与操作系统有关，一般为4k或者8k。这也就意味着读取一页内数据的时候，实际上发生了一次磁盘IO。

      正因为有了磁盘IO预读机制，所以才有了减少磁盘IO的可能，因为一次磁盘IO操作，可以查找到物理存储中相邻的一大片数据。

    以索引为B+树为例：

    磁盘IO次数和索引数据结构查询的次数以及磁盘IO与预读都有关系，具体关系：磁盘IO次数 <= B+树中从根节点一直到叶子节点整个过程中查询的节点数。

       一次磁盘IO操作可以取出物理存储中相邻的一大片数据，如果查询的索引数据（就是B+树中从根节点一直到叶子节点整个过程中查询的节点数）都集中在该区域，那么只需要一次磁盘IO，否则就需要多次磁盘IO

4.基于磁盘IO预读机制，索引可以快速查询数据

到现在开始讲解索引了。正是基于磁盘IO预读机制的前提，数据库可以采用索引机制快速查询出数据

4.1：什么是索引？

索引是帮助数据高效查询数据的一种数据结构，它包含一个表中某些列的值以及记录对应的地址，并且把这些值存储在一个数据结构中。常用的索引有B树和B+树

4.2：为什么使用索引

举个例子来说，假设我们有一个数据库student，这个表分别有三个字段：name，age，class。假设表中有2000条记录。

1、假如没有使用索引，当我们查询名为“xiaxia”的学生的时候，即调用：

select name,age,class from student where name = "xiaxia";

此时数据库不得不在student表中对这2000条记录一条一条的进行判断name字段是否为“xiaxia”。这也就是所谓的全表扫描。

2.而当我们在student表上的name字段上创建索引时，当我们查询名为“xiaxia”的学生时：

   会通过索引查找去查询名为“xiaxia”的学生，因为该索引已经按照字母顺序排列，因此要查找名为“xiaxia”的记录时会快很多，因为名字首字母为“x”的雇员都是排列在一起的。通过该索引，能获取到表中对应的记录。

5.数据库中使用什么数据结构作为索引

5.1：链表

链表的查询速度是O（N），每次查询都得从链表头开始查询，例如上面查询“xiaxia”，如果xiaxia在1000的位置，那么需要遍历1000次才能查找到。

5.2：数组

有人可能会说，查询速度肯定是数据最快呀，毕竟O（1），的确单纯就select的话，采用数组的形式是最合适的，但是采用数组会遇到如下几个问题：1、采用数组的话，其他操作如Delete、Update、Insert就不合适了；2、另外一个原因：索引是存在于磁盘中，当索引非常大的时候，达到几个G的时候，无法一次加载到内存中。
5.3：平衡二叉树

    二叉查找树查询的时间复杂度是O（logN），查找速度最快和比较次数最少，既然性能已经如此优秀，但为什么实现索引是使用B-Tree而不是二叉查找树，关键因素是磁盘IO的次数。

5.4：B树和B+树

数据库索引采用的数据结构

5.4：B-Tree与二叉树的对比

　　我们知道二叉查找树查询的时间复杂度是O（logN），查找速度最快和比较次数最少，既然性能已经如此优秀，但为什么实现索引是使用B-Tree而不是二叉查找树，关键因素是磁盘IO的次数。

数据库索引是存储在磁盘上，当表中的数据量比较大时，索引的大小也跟着增长，达到几个G甚至更多。当我们利用索引进行查询的时候，不可能把索引全部加载到内存中，只能逐一加载每个磁盘页，这里的磁盘页就对应索引树的节点。

6.采用平衡二叉树和B树，数据查询的对比

6.1：二叉树

我们先来看二叉树查找时磁盘IO的次：定义一个树高为4的二叉树，查找值为10：

---

---

---

从二叉树的查找过程来看，输的高度和磁盘IO的次数都是4，所以最坏的情况下磁盘IO磁盘IO的次数由树的高度来决定

从分析情况来看，减少磁盘IO的次数就必须要压缩树的高度，让瘦高的树尽量变成矮胖的树，所以B-Tree就在这样伟大的时代背景下诞生了

6.2: B-Tree

m阶B-tree满足一下条件

1. 每个节点最多拥有m个子树
2. 根节点至少有2个子树
3. 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
4. 所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列

 如下有一个3阶的B树，观察查找元素21的过程：

从查找过程中发现，B树的比对次数和磁盘IO的次数与二叉树相差不了多少，所以这样看来并没有什么优势。

但是仔细一看会发现，比对是在内存中完成中，不涉及到磁盘IO，耗时可以忽略不计。另外B树种一个节点中可以存放很多的key（个数由树阶决定）。

相同数量的key在B树中生成的节点要远远少于二叉树中的节点，相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后，性能的差异就显现出来了。

总结

插入或者删除元素都会导致节点发生裂变反应，有时候会非常麻烦，但正因为如此才让B树能够始终保持多路平衡，这也是B树自身的一个优势：自平衡；B树主要应用于文件系统以及部分数据库索引，如MongoDB，大部分关系型数据库索引则是使用B+树实现。

参考:https://blog.csdn.net/sinat_27602945/article/details/80118362