1. 磁盘基础知识

• 分页：

现代操作系统都使用虚拟内存来印射到物理内存，内存大小有限且价格昂贵，所以数据的持久化是在磁盘上。虚拟内存、物理内存、磁盘都使用页作为内存读取的最小单位。一般一页为4KB（8个扇区，每个扇区125B，8*125B=4KB）。

• 局部性原理：

1. 当一个数据被用到时，其附近的数据也通常会马上被使用。

2. 程序运行期间所需要的数据通常比较集中。

• 磁盘预读原理：

磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘IO的时间，大概 9ms 左右。这个成本是访问内存的十万倍左右；

磁盘读取的速度远小于内存，所以尽量减少 I/O 次数是提高效率的关键。

根据局部性原理，且由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），所以即使只需要读取一个字节，磁盘也会读取一页的数据。即磁盘预读时通常会读取页的整倍数。

2. 树基础知识回顾

排序二叉树：左 < 跟 < 右 B 树：有序数组 + 多叉平衡树，节点存储关键字、数据、指针；B+ 树：有序数组链表 + 多叉平衡树，非叶子节点存储指针、关键字，不存储数据；红黑树：红黑树是一种不大严格的平衡树（平衡树要求太高）

平衡树是为了防止二叉查找树退化为链表，而红黑树在维持平衡以确保 O(log2(n)) 的同时，不需要频繁着调整树的结构；

二叉树的存储结构

1. 顺序存储（适用于完全二叉树）

index 之间的对应关系：

注意：二叉树的顺序存储只适合存储完全二叉树，否则 index 无法和节点对应起来，会有点恶心：

1. 链式存储

这里要好好理解一下，不然会影响后面的理解。

3. 为什么不能使用二叉树来存储数据库索引

先说结论：

1. 平衡二叉树进行插入/删除时，大概率需要通过左旋/右旋来维持平衡；

2. 旋转需要加载整个树，频繁旋转效率低；

3. 二叉树的 I/O 次数近似为 O(log2(n))；

4. 范围查询时，二叉树的时间复杂度会退化成 O(n)；

5. 二叉树退化成链表时，时间复杂度也近似退化成了 O(n)；

6. 二叉树无法使用磁盘预读功能；

其实单论范围查询，在关系型数据库中就基本没有使用二叉树的可能了。但是为了加深对知识的了解，来看看其他的原因。

先剔除掉范围查询的情况，原因 1、2、6 可以通过红黑树来解决，那么其实就剩下 2 个原因：

1. I/O 次数对比；

2. 磁盘预读功能的利用；

4、二叉树的 I/O 次数分析

先说 I/O 次数：其实相比于二叉树，B 树、B+树， CPU 的运算次数并没有变化，甚至增多。但是 CPU 运算次数相比于 I/O 的消耗而言，可以忽略不计，所以 I/O 次数是评价一个数据库索引的效率高低的关键指标。

对于红黑树而言，其 I/O 次数近似为 log2(n)，为什么是近似呢？

首先，索引是存储在磁盘上的，磁盘上的数据大部分情况下是连续的，但是随着增删改查的发生，有可能产生很多碎片，也就是说：

• 索引在磁盘上的存储也不一定是连续的；

这里，严谨起见，我们来分两种情况：

1. 索引节点，即树的节点在磁盘上存储是连续；

假设一个页能存储 5 个节点，假设二叉树如下：

注意，序号只代表在磁盘中存储的顺序，不代表对应节点的关键字的值；

二叉树可能是链式存储，也可能是顺序存储。但是这里假设节点在磁盘上的存储是连续的，所以这里可以近似理解成顺序存储。即使是链式存储，无非就是 pNext 指针指向下一个连续的内存地址而已。

现在假设搜索的结果是最左边的叶子节点 16，因为磁盘预读的特性，加上一个页能存储 5 个节点，第一次 I/O ：

如上，第一次 I/O 就读取了 5 个节点，不仅把根节点读取进内存了，还把节点 2 和 4 都读取进去了，看上去还节约了两次 I/O ？好厉害的样子......

此时，会根据二分法查找，对比 1 号节点然后去找节点 2，紧接着找节点 4，因为这两个节点都在内存中了，所以不需要进行 I/O

这里再说一次，序号不代表节点的关键字，而是单纯的表示节点在磁盘中的排列顺序；

紧接着，会需要 8 号节点，而 8 不再内存中，所以进行第二次 I/O 同样是读取一页，即 5 个节点：

这次虽然也是读取了 5 个节点，但是实际上只有 8 号节点有实际作用，其他节点并没什么卵用（这是二叉树无法使用预读功能的本质），但是现在还没体现出劣势，现在对比之后需要 16 号节点，继续第三次读取：

此时找到了 16，并将结果返回。

这是高度为 4 的情况，且只有 31 个数据。但是实际使用中，怎么可能就 31 个数据？假设要找的是 32 号节点，因为 16 号节点之后的 17-20 虽然被加载进内存了，但是完全没用。那么就需要再进行一次 I/O 来加载 32 号节点所在的页，同时也会将 33-36 加载进内存，但是这些节点并无卵用。

如果要找的是 1000 ，10000？

所以，随着层级的深入，会出现：

1. 一个页中只有一个节点有用（二分法查找要的是子节点而不是兄弟节点）；

2. I/O 次数近似等于log2(n)；

即：

1. 第一次 I/O 可能的优势在层级加深之后就没有了；

2. 就算是红黑树，也只能将时间复杂度维持在 log2(n)；

上述讨论的是索引树在磁盘上的存储是连续的，如果不是连续的，那么按页读取到的脏数据会更多，上述的情况中，前几次 I/O 读取到有用的数据的概率会变低，所以 I/O 的次数只会增多而不会减少,即仍然是近似于 log2(n)。

5. B/B+树

B 树即：多路平衡查找树。

B 树的巧妙之处在于：

1. 将一个节点的大小设置为一页的大小；

2. 一个节点可以存放多个关键字（多叉树）；

3. 自平衡；

这 3 点结合起来就可以做到：

1. 一个节点大小为一页，被加载进内存时，这些关键字在进行对比，找出需要 leftChild 还是 rightChild 时，都是有用的（如最右侧时需要对比所有节点）；

2. 一个节点可以存储多个关键字，有效降低了树的高度；

B+ 树的巧妙之处在于：

1. 非叶子节点不存储数据，进一步增大了一页中存储关键字的数量；

2. 叶子节点中存储数据且存在指向下一页的链表指针，可以使用顺序查询（支持范围查询）；

6. B/B+树的索引数量

B 树的节点中存储：指针、关键字(主键)、数据 B+ 树的非叶子节点：指针、关键字 B+树的叶子节点：指针(链表)、关键字、数据

注意，这里不是绝对的，比如有的 B+ 树中叶子节点存储的不是数据，而是指向数据的指针。查询到指针之后再去对应地址取出数据，但是这样应该会增加一次 I/O 吧，应该也是在数据量和 I/O 次数之间做了取舍，具体先不讨论。

以 Sqlite3.12 之后为例，page_size = 16k，假设指针为 8 byte，假设关键字类型占 8 byte，假设数据占 1 KB；

B 树的一个节点：

一页能存储的数据量为：16kb / (1KB+8byte+8byte) ≈ 16；

高度为 3 的 B 树能存储 16 x16 x16 = 4096 条数据

相比于二叉树的 1 个而言，确实有效降低了树的层级。而且上述是假设数据为 1KB，如果数据没那么大，高度为 3 的 B 树能存储更多的数据，但是如果用在大型数据库索引上还是不够。

B+ 树：

如上图，B+树的核心在于非叶子节点不存储数据。

这样做可以减少非叶子结点占用的空间，增大一页所能存储的数据量，最大程度减少树的层级。

仍然是以上假设，假如树的高度为 3 ，那么就有两层存储关键字+指针，一层叶子节点来存储实际数据。

一页能存储的关键字为：16 * 1024 / (8 + 8) = 1024 一页能存储的数据量为：16KB / (1KB + 8byte + 8byte) = 16 （这里计算不完全准确，实际情况应该是1页数据中只有一个链表指针指向下一页） 能存储的关键字为：1024 * 1024 = 1048576；

因为端节点又有 1024 个指针，这些指针可以指向一个页，页中存储数据，也就是叶子节点，一页能存储 16 个叶子节点，所以总共能索引的数据量为 1048576 * 16 ≈ 1600万；如果高度为 4 ，则再乘以 1024 约为 17亿.....

上述推理中，理解终端节点的指针指向一个页，页中存储着关键字 + 数据 + 链表指针是关键。page 标记如下，有助理解：

虽然叶子节点很多，一个 page 对应一个叶子节点甚至是多个 page 才能存下一个叶子节点，但是这些是存在磁盘上的，找到对应的 page 之后才去加载对应的 page。索引超大数据量的同时，不会对 I/O 次数产生影响，这就是这个设计的牛逼之处。

但是这样也是有缺点的：

无论查询结果如何，都必须走到叶子节点才结束，也就是 I/O 次数固定为 O(h) 或者说是 log(n)（底数为节点子分支个数），这个 h 一般为 2-3，排除掉根节点常驻内存，高度为 3 的 B+ 树进行两次 I/O 就可以索引千万级别的数据,高度为 4 的 B+ 树，进行 3 次 I/O 就能索引十亿级别的数据量，这个效果还是很好的。

所以，这个缺点也可以说成是优点：稳定（稳如一条老狗🐶）

7. 实际应用

• 红黑树优点

红黑树常用于存储内存中的有序数据，增删很快，内存存储不涉及 I/O 操作。

• B/B+树的优点

更适合磁盘存储，减少了树的层级，进而减少 I/O 次数；

• B 树和 B+ 树对比

都是 B 树，但是 B+树更适合范围查询，比如 Mysql，且查询次数很稳定，为 logn。而 B 树更适合键值对型的聚合数据库，比如 MongoDB，查询次数最优为 O(1)；

红黑树更适合内存存储，B 树更适合键值对存储，B+ 树适合范围查询；

数据库：为什么使用B+树而不使用红黑树

B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。所以从Mysql（Inoodb）的角度来看，B+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。 

那么Mysql如何衡量查询效率呢？– 磁盘IO次数。B-树/B+树 的特点就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。这是优点之一。 

另一个优点是：B+树所有的Data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的，而B树不支持这样的遍历操作。

B树相对于红黑树的区别

B树是多路树，红黑树是二叉树！红黑树一个节点只能存出一个值，B树一个节点可以存储多个值，红黑树的深度会更大,定位时 红黑树的查找次数会大一些。

AVL 树和红黑树基本都是存储在内存中才会使用的数据结构。

在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。为什么会出现这样的情况，我们知道要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，B树可以有多个子女，从几十到上千，可以降低树的高度。

数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

为什么mysql用B+树做索引而不用B-树或红黑树

　　B-树、B+树、红黑树，是平衡查找树，那么查询效率上讲，平均都是O(logn)。使用什么哪种数据结构，肯定是出于提高数据库的查询效率的考虑。

一、B+树做索引而不用B-树
　　Mysql如何衡量查询效率呢？– 磁盘IO次数。
　　一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。B-树/B+树 的特点就是每层节点数目非常多，层数很少，目的就是为了减少磁盘IO次数，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。

　　优点一：B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。

　　优点二：B+树所有的Data域在叶子节点，并且所有叶子节点之间都有一个链指针。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的，而B树不支持这样的遍历操作。

B+树做索引而不用红黑树
　　AVL 树（平衡二叉树）和红黑树（二叉查找树）基本都是存储在内存中才会使用的数据结构。在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。为什么会出现这样的情况，要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，B树可以有多个子女，从几十到上千，可以降低树的高度。

　　数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

B-TREE索引

　　B-TREE索引是使用最多的索引。很多存储引擎采用的都是B-TREE数据结构的变体实现该索引，例如InnoDB使用的是B+TREE，即每个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点范围遍历。
　　B-TREE中的所有值都是按顺序存储的，每个叶子页到根的距离相同。下图展示了InnoDB中的B-TREE索引是如何工作的：

　　当查找一行记录时，存储引擎会先在索引中搜索。从索引的根节点开始，通过比较节点页的值和要查找的值逐层进入下层节点，最底层叶子节点的指针指向的是被索引的数据。这样的查找方式避免了全表扫描，加快访问数据的速度。此外因为B-Tree对索引列是顺序存储的，所以也很适合查找范围数据。
下面是一个使用B-Tree索引的例子，有如下数据表：

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)
)

建表语句在last_name、first_name、dob列上建立了一个联合索引，下图展示了该索引的存储结构

　　联合索引中的索引项会先根据第一个索引列进行排序，第一个索引列相同的情况下，会再按照第二个索引列进行排序，依次类推。根据这种存储特点，B-Tree索引对如下类型的查找有效：

1. 全值匹配：查找条件和索引中的所有列相匹配

2. 匹配最左前缀：查找条件只有索引中的第一列

3. 匹配列前缀：只匹配某一列值的开头部分。这里并不一定只能匹配第一个索引列的前缀。例如在确定第一个索引列的值时，也可以在第二个索引列上匹配列前缀。在上面例子中，对于查找姓为Allen，名为J开头的人，也可以应用到索引。

4. 匹配范围值，或者精确匹配某一列并范围匹配另外一列：例如查找姓在Allen和Barrymore之间的人，或者查找姓为Allen，名字在某一个范围内的人。

5. 只访问索引的查询，即要查询的值在索引中都包含，只需要访问索引就行了，无需访问数据行。这种索引被称作覆盖索引。

6. 对于上面列出的查询类型，索引除了可以用来查询外，还可以用来排序。

下面是B-Tree索引的一些限制：

1. 如果不是从索引的最左列开始查找，则无法使用索引。例如直接查找名字为Bill的人，或查找某个生日的人都无法应用到上面的索引，因为都跳过了索引的第一个列。此外查找姓以某个字母结尾的人，也无法使用到上面的索引。

2. 不能在中间跳过索引中的某个列，例如不能查找姓为Smith，生日为某个特定日期的类。这样的查询只能使用到索引的第一列。

3. 如果查询中有某个列的范围查询，则该列右边的所有列都无法使用索引优化查找。例如有查询WHERE last_name='Smith' AND first_name LIKE 'J%' AND dob='1976-12-23'，这个查询只能使用到索引的前两列，而不能使用整个索引。

数据结构：内存操作红黑树快，磁盘操作B树或者B+树快

B+树的高度要比红黑树小，有效减少了磁盘的随机访问；
B+树的数据节点相互临近，能够发挥磁盘顺序读取的优势（缓存）；
B+树的数据全部存于叶子结点，而其他节点产生的浪费在经济负担上能够接受，红黑树存储浪费小；

红黑树常用于存储内存中的有序数据，增删很快；B+树常用于文件系统和数据库索引。

红黑树只能有2个子节点；

B树子节点大于2，子节点树多这一特点保证了存储相同大小的数据，树的高度更小，数据局部更加紧凑，而硬盘读取有局部加载的优化（把要读取数据和周围的数据一起预先读取），b树相邻数据物理上更加紧凑这一特点符合硬盘进行IO优化的特性。

B+树在b树基础上进一步将数据只存在叶子节点，非叶子节点不存值只存储关键字或者键值和值的指向，而且叶子节点前后相连放入链表中。使得数据更加紧凑有序，只需要链表（叶子节点）的一次遍历就能获取所有树上的值。

B-树（B树）和B+树的区别

（1）B+树查询时间复杂度固定是logn，B-树查询复杂度最好是 O(1)。

（2）B+树相邻接点的指针可以大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。

（3）B+树更适合外部存储，也就是磁盘存储。由于内节点无 data 域，每个节点能索引的范围更大更精确。

总之，B-树每个节点即保存数据又保存索引，所以磁盘IO的次数很少；B+树只有叶子节点保存，磁盘IO多，但是区间访问比较好。

所以：

MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql。

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