名称解释:
B-Tree :树
Leaf : 树叶
: 树叶
叶子节点/终端节点 : 没有子节点的节点,记为树叶
非叶子节点/非终端节点:含有子节点的节点,可以理解为树枝
特点:
1.所有非叶子结点至多拥有两个儿子(Left和Right);
2.所有结点只存储一个关键字;
3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;
BST树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;
如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变BST树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;