平衡二叉树，红黑树，B树和B+树的区别及其应用场景

平衡二叉树

• 基础数据结构
• 左右平衡
• 高度差大于1会自旋
• 每个节点记录一个数据

平衡二叉树（avl）

avl树全称g.m. adelson-velsky和e.m. landis，这是两个人的人名。

平衡二叉树也叫平衡二叉搜索树（self-balancing binary search tree）又被称为avl树， 可以保证查询效率较高。

具有以下特点：

• 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1
• 并且左右两个子树都是一棵平衡二叉树。
  
  avl的生成演示：https://www.cs.usfca.edu/~galles/visualization/avltree.html

avl的问题

众所周知，io操作的效率很低，在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐节点加载（一个节点一次io）。如果我们利用二叉树作为索引结构，那么磁盘的io次数和索引树的高度是相关的。平衡二叉树由于树深度过大而造成磁盘io读写过于频繁，进而导致效率低下。

为了提高查询效率，就需要 减少磁盘io数 。为了减少磁盘io的次数，就需要尽量降低树的高度 ，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。针对同样的数据，如果我们把二叉树改成 三叉树：

上面的例子中，我们将二叉树变成了三叉树，降低了树的高度。如果能够在一个节点中存放更多的数据，我们还可以进一步减少节点的数量，从而进一步降低树的高度。这就是多叉树。

普通树的问题

• 左子树全部为空，从形式上看，更像一个单链表，不能发挥bst的优势。
• 解决方案：平衡二叉树(avl)
  

红黑树

• hashmap存储
• 两次旋转达到平衡
• 分为红黑节点

在这个棵严格的平台树上又进化为“红黑树”{是一个非严格的平衡树 左子树与右子树的高度差不能超过1}，红黑树的长子树只要不超过短子树的两倍即可！

当再次插入7的时候，这棵树就会发生旋转

b+ 树和 b 树的差异：

• b+树中非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大值（或最小）。
• b+树中非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而b树中， 非叶子节点既保存索引，也保存数据记录 。
• b+树中所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

一个b+树中大概能存放多少条索引记录？

• 真实环境中一个页存放的记录数量是非常大的（默认16kb），假设指针与键值忽略不计（或看做10个字节），数据占 1 kb 的空间：
• 如果b+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放 16 条记录。
• 如果b+树有2层，最多能存放 1600×16=25600 条记录。
• 如果b+树有3层，最多能存放 1600×1600×16=40960000 条记录。
• 如果存储千万级别的数据，只需要三层就够了

b+树的非叶子节点不存储用户记录，只存储目录记录，相对b树每个节点可以存储更多的记录，树的高度会更矮胖，io次数也会更少。

使用b+树存储的索引crud执行效率如何？
c 新增

o(lognn)

n = 高度

什么是自适应哈希索引？

自适应哈希索引是innodb引擎的一个特殊功能，当它注意到某些索引值被使用的非常频繁时，会在内存中基于b-tree所有之上再创建一个哈希索引，这就让b-tree索引也具有哈希索引的一些优点，比如快速哈希查找。这是一个完全自动的内部行为，用户无法控制或配置

使用命令
show engine innodb status \g ;

查看 insert buffer and adaptive hash index