小白升级巨匠第 1 篇文章,开始写一些有深度的文章了
先举荐一个数据结构可视化工具网站,用于 B + 树可视化查看
Data Structure Visualizations
面试技术岗的时候,面试官问你:
mysql 索引底层用的是 B + 树结构,为什么不必 B 树、二叉树、红黑树呢?
这里其实就是比拟各种数据结构的优劣点,最初阐明为什么要用 B + 树结构;
假如数据查问场景:当初有 100W 的数据存储,查问其中的一条,应该用哪种存储构造呢?
二叉查找树
二叉查找树即有序二叉树,满足二叉树的性质,具备上面特点:
- 任意节点左子树不为空时,左子树值小于根节点值
- 右子树不为空时,右子树值大于根节点值;
顺次存入数据,如果数据是递增的,则原二叉树进化为链表构造,如图
这种状况下,查问的工夫复杂度就是 O(n) 了
AVL 树
AVL 树即均衡二叉查找树,通过均衡因子差值判断是否均衡,再用旋转来实现树的均衡。左右子树的树高差不超过 1。在执行插入删除操作时,对不满足条件的子树,通过旋转保持平衡。性能开销次要在旋转操作上,由此能够晓得 AVL 树适宜查问多,插入删除少的场景
如图,我创立了一棵 AVL 树,感兴趣的能够在网站上看一下插入过程和旋转调整均衡的过程。
AVL 树须要维持树的均衡,而保护这种均衡的开销要大于取得的收益,理论利用中不多
红黑树
红黑树是一种二叉查找树,每个节点新增一个存储位标记是 red 或 black,通过任何一条从根节点到叶子节点门路上,各个节点着色形式的限度,确保没有一条门路比其余门路长 2 倍,红黑树性质:
- 根节点是彩色,每个节点非红即黑;
- 叶子节点都是彩色
- 如果一个节点是红色,那它的子节点都是彩色
- 任意节点到叶子节点的门路都蕴含雷同数目的彩色节点
如图是红黑树的可视化:
AVL 树和红黑树一样,随着记录数的减少,树的高度会一直减少,查问次数也会减少。
文章结尾咱们说的要查问 100w 条数据中的一条,就须要 20 次搜寻,搜寻效率不高,查问次数剖析如下
$$
2^{20} = 1048576
$$
B- 树
即 B 树,和红黑树相比,B 树的树高远远小于红黑树的高度。B 树是为了和磁盘交互而设计的均衡多路查找树,操作效率有磁盘的拜访次数决定,树高越小,磁盘 I / O 工夫越短。
B 树性质:
- 非叶子节点上最多有 M 个子节点,且 M >2;
- 根节点的子节点数目为 [2, M];
- 每个节点寄存至多 M /2-1,至少 M - 1 个关键字
- 非叶子节点关键字数目 = 指向子节点的指针个数 -1;
- 所有叶子节点位于同一层
比照红黑树能够发现,每个节点上能够存储更多的数据,且树高固定,数据插入之后横向扩大。即每一次查问只须要搜寻 3 次就行。搜寻效率大大提高了。接着咱们再来看看 B + 树
B+ 树
说一下 B + 树的性质:
- 非叶子节点的子树指针 和 关键字 个数一样;
- 非叶子节点的子树指针,指向闭区间 [k[i], k[i+1]],即 B 树不容许关键字反复,B+ 树容许
- 为所有叶子节点减少一个链指针;
- 非叶子节点作为索引,叶子节点才存储关键字
- 所有关键字存储在叶子节点
B+ 树比起 B 树的长处有:
- 只在叶子节点存储数据,16k 的内存能够存下更多数据,升高树高
- 冗余索引,不便查找;
- B+ 树叶子节点减少了双向链表,不便范畴查问;
于是,回到结尾的问题,100W 的数据,B+ 树只须要 3 次或 4 次 I / O 查问就能定位到了,且相比拟 B 树,B+ 树更适宜简单的查问场景,如范畴查问。