利用假期，将之前看的零零散散的数据库底层组织结构串联起来，梳理了：二叉树，平衡二叉树，Hash索引，BTree，B+树的区别，用大白话梳理了为啥要发展出后者，进行逐次不断的迭代进化，用大白话解读，仅涉及原理的理解，供自己理清框架，也供小白们参考借鉴。

首先声明：我只是百度、CSDN、知友们的搬运工，站在大佬们的基础上，感谢网友！

① 对一个数据库，如果录入数据表时，啥也没有，直接顺序存入、读取，将非常耗时，低效：

②二叉树

为了提高I/O效率，先引入简单的二叉树的索引方式。二叉树，即左子树的键值小于根的键值，右子树的键值大于根的键值，并且左右子树都是二叉排序的。

优点：基于二叉查找树的这种特点，我们在查找某个节点的时候，可以采取类似于二分查找的思想，快速找到某个节点。

对该二叉树的节点进行查找，深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n。

缺点：由于二叉查找树可以任意地构造，在极端情况下，如果插入的数据按照递增或者递减的顺序出现，就会变成链表。这棵二叉树的查询效率就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的。

③ 平衡二叉树(AVL树)

平衡二叉树就是为了解决二叉查找树退化成一颗链表而诞生的，平衡树具有如下特点：在符合二叉查找树的条件下，还满足任何节点的两个子树的高度大差为1。

如果在AVL树中进行插入或删除节点，可能导致AVL树失去平衡，AVL树失去平衡之后，可以通过旋转使其恢复平衡。关于各种旋转，各位可以看书或网上搜索案例，原理不难，但分类多，这里不展开。

优点：解决了二叉查找树退化为近似链表的缺点；

缺点：平衡二叉树追求平衡，条件比较苛刻，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，每次插入新节点之后需要旋转的次数不能预知。显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁调整，这使平衡树的性能大打折扣。

④ 红黑树

与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。红黑树原理较为生涩，这里不展开，但是是发展历程之一。

优点：红黑树放弃了追求完全平衡，追求大致平衡，解决了平衡树在插入、删除等操作需要频繁调整的情况。

缺点：数据量大的话，红黑树的深度会很深，也就是说深度不可控，这样一来查找数据还是会很耗时。

⑤ hash

之前的树，他们的查找，都是先从根节点进行查找，从节点取出数据或索引与查找值进行比较。相较于之前的，哈希索引是一股清流，原理挺不一样的：

哈希表(Hash table，也叫散列表)，对于任意给定的键值(Key)，通过函数，映射到表中的一个位置，从而实现数据直接访问。

说白了，hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表。若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。注意，hash表需要解决冲突：对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突。

hash相当于把key通过hash函数计算，得到key的hash值，再用这个hash值做指针，查找hash表中是否存在key，如果存在就返回 key所对应的value，选定一个好的hash函数很重要，好的hash函数可以使计算出的hash值分布均匀，降低冲突，只有冲突减小了，才会降低 hash表的查找时间。

优点：快速查询。相比较于红黑树，hash可以固定“深度”，检索效率非常高，索引的检索可以一次到位。

缺点：

1. 哈希索引只包含哈希值和行指针，所以不能用索引中的值来避免读取行

2. 哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序和范围查询

3. 哈希索引也不支持部分索引列查询，因为哈希索引始终是使用索引列的全部数据进行哈希计算的。

4. 哈希索引只支持等值比较查询，如=，IN()，<=>操作

5. 如果哈希冲突较多，一些索引的维护操作的代价也会更高

⑥ B树（终于到重点了额，敲黑板！）

B树，其实是一棵多叉搜索树，多叉搜索树允许节点中的元素数量超过1，也就是一个节点可以存储多个元素，并且会有多个子树分支。B树还有一个非常巧妙的设计，就是每一个节点的孩子个数是元素的数量+1，并且和二叉搜索树一样，存在大小顺序的关联。

和二叉搜索树相比，它究竟有什么得天独厚的优点呢？

B树主要用在各大存储文件系统和数据库系统当中。在这些场景下数据总量很大，我们不可能将它们都存储在内存当中。所以为了解决这个问题，我们会在树节点当中存储孩子节点的在磁盘上的地址。在需要访问的时候通过磁盘加载将孩子节点的信息读取到内存当中。也就是说在数据库当中我们遍历树的时候也伴随着磁盘读取。

对于内存来说，寻址访问的时间可以认为的均衡稳定的，但是磁盘的访问速度是很慢的，所以要减少对磁盘的访问。

1. 树的深度越大，磁盘读写的次数也就越多，那么带来的IO开销也就越大，同样的元素，明显B树的树深更小。

2. 你需要减少树的深度，平衡树是更优的选择。但是平衡树的建立又产生另外一个问题也就是节点的旋转，在插入/删除时会频繁的使用。因此，我们希望在树的建立上留有一定的余量，使得快速的插入/删除成为可能，而不需要每次都频繁的调整树的结构。

B树的每个节点因为拥有>=2的子节点，其节点信息允许在子节点未完整填充时，可以进行快速的内容填充而不需要重新调整树的平衡性，也不会因为删除节点破坏树的平衡性，因此在插入/删除操作上更节约磁盘IO的使用。

缺点：

1.每个节点中既要存索引信息，又要存其对应的数据，如果数据很大，那么当树的体量很大时，每次读到内存中的树的信息就会不太够。

2.B树遍历整个树的过程和二叉树本质上是一样的，B树相对二叉树虽然提高了磁盘IO性能，但并没有解决遍历元素效率低下的问题。

⑦ B+树

B+树相比B树，本质上是一样的，区别就在：

1. 与B+树的所有根节点都不带有任何数据信息，只有索引信息，所有数据信息全部存储在叶子节点里，这样，整个树的每个节点所占的内存空间就变小了，读到内存中的索引信息就会更多一些，相当于减少了磁盘IO次数，问题1就得到了解决。

2. B树所有叶子节点都在同一层，B+树会以一个链表的形式将所有叶子节点的信息全部串联起来，这样，想遍历所有数据信息只需要顺序遍历叶子节点就可以了，方便又高效，问题二就得到了解决。

到此，终于告一段落了，也就是我们mysql普遍使用的：B+树。注意下，这里的B即Balanced，平衡的意思，而不是binary。