mysql为什么使用B+树

两种树形结构

B树

每个节点都存储key和data，所有节点组成这棵树，并且叶子节点指针为null

B+树

只有叶子节点存储data，叶子节点包含了这棵树的所有键值，叶子节点不存储指针。

后来，在B+树上增加了顺序访问指针，也就是每个叶子节点增加一个指向相邻叶子节点的指针 ，这样一棵树成了数据库系统实现索引的首选数据结构。

原因有很多，最主要的是这棵树矮胖 ，呵呵。一般来说，索引很大，往往以索引文件的形式存储的磁盘上，索引查找时产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的时间复杂度。树高度越小，I/O次数越少。

那为什么是B+树而不是B树呢，因为它内节点不存储data，这样一个节点就可以存储更多的key。

在MySQL中，最常用的两个存储引擎是MyISAM 和InnoDB ，它们对索引的实现方式是不同的。

---

Mysql存储引擎

MyISA

data存的是数据地址。索引是索引，数据是数据。索引放在XX.MYI文件中，数据放在XX.MYD文件中，所以也叫非聚集索引。

InnoDB

data存的是数据本身。索引也是数据。数据和索引存在一个XX.IDB文件中，所以也叫聚集索引。

两种引擎区别

了解了数据结构再看索引，一切都不费解了，只是顺着逻辑推而已。另加两种存储引擎的区别：

1. MyISAM是非事务安全的，而InnoDB是事务安全的

2. MyISAM锁的粒度是表级的，而InnoDB支持行级锁

3. MyISAM支持全文类型索引，而InnoDB不支持全文索引

4. MyISAM相对简单，效率上要优于InnoDB，小型应用可以考虑使用MyISAM

5. MyISAM表保存成文件形式，跨平台使用更加方便

6. MyISAM管理非事务表，提供高速存储和检索以及全文搜索能力，如果在应用中执行大量select操作可选择

7. InnoDB用于事务处理，具有ACID事务支持等特性，如果在应用中执行大量insert和update操作，可选择。

---

为什么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。