二叉树
什么是二叉树?
- 每个节点至多只有两棵子树,左子树和右子树。左子树和右子树。
- 逻辑上二叉树有五种基本形态,空二叉树、只有一个根节点的二叉树、只有左子树、只有右子树、完全二叉树(满二叉树)
- 遍历二叉树有前序遍历、中序遍历、后续遍历。
数据库的索引是要求排好序的数据结构。引入了二叉查找树。
二叉查找树
- 在二叉树的基础上,加上左子树的节点值总是小于根的节点值,右子树的节点值总是大于跟的节点值,也就是左子树节点值 < 根的节点值 < 右子树节点值。
设计合理的时候可以将一组数据转化为二叉查找树,时间复杂度和二分查找一致。
但是存在设计不合理的场景:
当二叉查找树不平衡,可能退化为一个线性的链表,查找时间复杂度高了起来。
二叉搜索树可能不平衡,所以再看下平衡二叉树
平衡二叉树(AVL树)
- 符合二叉查找树的定义,然后再满足任何节点的两个子树的高度之差的绝对值不超过1。
相对于二叉查找树,平衡二叉树查找效率稳定。
但也有缺点:
- 查询速度快,但是插入数据时需要维护平衡二叉树,需要1次或多次左旋或者右旋来完成更改节点之后的平衡性。
- 平衡二叉树随着数据增多,高度会增加,作为索引的数据结构可能查找一个数据可能要好多次IO。
B-tree和B+Tree
平衡二叉树存在树过高导致的IO问题,B-Tree用来解决的思想是在每一个节点上存放多个元素,来降低树的高度,以来减少磁盘IO。
B-Tree
B-Tree是一个多路搜索树,m阶的B-tree有如下特性:
- 每个节点最多有m棵子树。
- 若根节点不是叶子节点,则至少有两个孩子。
- 每个节点上存有关键字(索引值),且节点的子树按照关键字排序。
- 每个节点上的关键字都有一个指针,指针指向子树的所有节点索引值都小于当前索引值,都大于上一个索引值。
- 所有叶子节点都在同一层。
B-Tree中索引和除了索引之外的列是放在一起的,非叶子节点没有冗余索引,同时上层节点中索引关联的指针指向叶子节点,索引节点的左边孩子节点都比索引值小,右边节点都比索引值大。
这样的多路搜索已经降低了树的高度。
但Mysql还是采用了B+Tree。
B+Tree
是B-Tree的变种,也是一种多路搜索树,有几点不同:
- 非叶子节点的子树指针与索引个数相同
- 非叶子节点只存储索引信息,不存放其余的列。
- 非叶子节点冗余了索引值。
- 所有叶子节点之间用双向指针连接,形成双向链表。
- 叶子节点存放索引之外,还存放了其余列。
为什么用B+Tree而不用B树?
非叶子节点不存放数据,单个节点能装下更多索引的值,降低了树的高度。
叶子节点双向指针连接,叶子节点中记录项用单向指针连接,提高了区间访问和范围查找的效率。
Hash结构
为什么不使用hash结构来存放索引呢?
- hash碰撞和扩容问题。
- hash数据结构也能快速根据索引列定位数据。hash算法的优点
- hash能支持 = in查询,但对于范围查询不好支持。