二叉树：一个节点内只有【一个】关键值，这个节点的【左子节点小于当前节点】【右子节点大于当前节点】，查询时，与当前节点进行比较，小于当前节点之值则继续进入左子节点，大于当前值则进入右子节点，依次往下找直到找到需求值
但是二叉树有一个缺点，就是在某种极端情况下会变成线性链表的形式
这时候使用二分查找就很浪费性能，故出现了【平衡二叉树(AVL树)】
平衡二叉树(AVL)：在二叉树的基础上要求每个子节点左右高度差不能超过1层
如果需要插入的去值会让AVL失衡，变成非平衡二叉树，也可以通过左旋右旋进行处理
左旋为逆时针旋转，右旋为顺时针
在插入的过程中，会出现一下四种情况破坏AVL树的特性，我们可以采取如下相应的旋转。
1、左-左型：做右旋。
2、右-右型：做左旋转。
3、左-右型：先做左旋，后做右旋。
4、右-左型：先做右旋，再做左旋。
红黑树：如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树，红黑树具有如下特点：
1、具有二叉查找树的特点。
2、根节点是黑色的；
3、每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据。
4、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。
5、每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。
B树(B-树)：一个节点内包含【多个关键值和多个指针域】，目的在于减少整棵树的高度
B+树：基于B树
特点:
每个父节点都会出现在子节点中，是该子节点的最大或者最小值，根节点的最大值就等于该B+树的最大值，以后不论插入多少元素，都需要保证根节点的最大值是整棵树中最大的
每个叶子节点都带有【指针】【指向下一个节点】，从而行成一个有序链表
B+树中的【卫星数据(data)】只在叶子节点存在，而B树是不论中间节点或者叶子节点，都带有卫星数据【聚集索引中，叶子节点直接包含卫星数据。在非聚集索引中，叶子节点带有指向卫星数据的指针】
------------------------------------------------------------------------------------------------------
B+树的好处：
因为不需要在中间节点存储卫星数据，则可以在单个节点存更多数据，比B树减少了中间节点的层数，降低IO次数
B树的查询性能不稳定，最低效率可能是整棵树的层高也可能在第二个节点就找到，而B+树则非常稳定，要求必须找到最后一层叶子节点
-------------------------------
B树找值⬇️
--------------------------
B+树找值⬇️
B+树通过链表指针找值
B树通过中序遍历找值
