树:树家族是为了实现方便快捷的查找而存在的,其中最简单的是二叉树,尽管易于实现,却不能有实际的价值。其最最令人发指的是二叉树的高度太高。n叉树的提出和实现解决了二叉树的不足,典型的n叉树有:2-3-4树/红黑树和B树。(我们一般谈论的都是有序树)
B树(B-数):是一种平衡的多叉树
相比二叉树,它的层数可以比较稳定地得到控制,做查询的时候不会像二叉树那般不稳定。
B树可以是多阶的,例如M=4 阶的B树如下:
构建过程如下:
数据结构小工具:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html