演示网址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

1、二叉查找树（BST）、平衡二叉树（AVL）、红黑树（RBT）的区别？

二叉查找树->平衡二叉树->红黑树

1）二叉查找树（BST）：
特点：
左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大
缺点：
二叉查找树因可能退化成链表，故其性能最差(树高很大)

2）平衡二叉树（AVL）特点：（是一种特殊的二叉查找树）
特点：
每个节点的左子树和右子树的高度差至多等于1，如果层高大于1，则进行旋转（左旋（逆时针），右旋（顺势针））
缺点：
平衡二叉树如果在那种插入、删除很频繁的场景中，平衡二叉树需要频繁着进行调整（旋转），这会使平衡树的性能大打折扣

3）红黑树（RBT）特点：（是一种特殊的平衡二叉树）
特点：
根节点是黑色的
每个叶子节点都是黑色的空节点（黑叶子节点不放数据）
任何相邻的节点都不能同时为红色
每个节点，从根节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点

优点：
与平衡二叉树不同，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整

一句话总结：平衡二叉树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡二叉树在插入、删除等操作需要频繁调整树结构的情况。

HashMap底层结构，数组+链表+红黑树

参考文章：https://baijiahao.baidu.com/s?id=1636557496125304849&wfr=spider&for=pc

2、BTree 与 B+Tree的区别？

特点：
B树叶子节点和非叶子节点都存数据（索引和数据都存储），且叶子节点数据无链指针；
B+树只有叶子节点存数据（叶子存储数据，非叶子存储索引），且叶子节点数据有链指针。

B树的优势：
在B树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；
B树的缺点：
当进行范围查找时，存在“回旋查找”的问题，效率低

B+树的优势：
所有叶子节点形成有序链表，便于范围查询（不存在回旋查询的问题）

正是因为B+有这样的特点，所以MySQL的索引采用B+树存储！！！
MySQL底层还对B+树进行优化，叶子节点采用双向链表，这样不管大于还是小于范围查询，都很快了！

复写： B树：叶子节点和非叶子节点都会存储数据，且叶子节点是无链指针； B+树：只有叶子节点才会存储数据，且叶子节点是有链指针；

3、为什么MySQL的索引采用B+树，而不是B树、Hash、二叉树、红黑树呢？

1）Hash哈希，只适合等值查询，不适合范围查询 id=5
2）一般二叉树，可能会特殊化为一个链表，相当于全表扫描
3）红黑树，是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘的次数就多了。
4）B树在范围查询时，存在回旋查找的问题，导致性能不高。B+树叶子节点是有序链表，更有利于范围查询。（MySQL的索引对B+树的叶子节点进行改造，形成双向链表！！！）

复写：

1. hash：只适合等值查询，不适合范围查询；
2. 二叉树：会特殊化为一个链表，相当于全表查询；
3. 红黑树：是一种特殊的平衡二叉树，在sql数据量很大的时候，索引的体积也会很大，内存放不下的时候会从磁盘读取，如果树的分层很多，那么要读取的磁盘次数也会随之而增加；
4. B树在范围查询的时候，会存在回旋查找的问题，导致性能下降；而B+树的叶子结点是有序链表，更有利于范围查询；mysql的索引对B+树的叶子节点进行改造，行成双向链表；

4、MySQL表引擎有哪些？这些引擎有什么区别？MySQL的MyISAM和InnoDB的索引使用B+Tree实现有什么不同？

MySQL表引擎常用：
1）InnoDB
2）MyISAM

MySQL表引擎的区别：
1）InnoDB支持事务，InnoDB支持表级和行级锁，InnoDB是采用聚簇索引
2）MyISAM不支持事务，MyISAM只支持表级锁，不支持行级锁，MyISAM采用非聚簇索引

InnoDB采用聚集（聚簇）索引存储，索引和数据存储一个文件中，默认使用表的主键列值来构建B+树（表没定义主键也会包含隐式主键）
.frm
MyISAM采用非聚集（非聚簇）索引存储，索引和数据文件是分两个文件存储的，可以没有主键索引
.myi .myk

复写： 常用的引擎有： innoDB； MyISAM；

• innoDB：支持事务，支持表级锁和行级锁，是聚集索引储存；
• MyISAM：不支持事务，只支持表级锁，不支持行级锁，是非聚集索引储存；