平衡二叉树
- 基础数据结构
- 左右平衡
- 高度差大于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