学习笔记之多路查找树

发表于 更新于 分类于

多路查找树

  • B树
  • B+ 树

如果数据量非常大, 内存无法全部处理 （例如数据库存储）, 这种情况对数据的处理需要不断从硬盘等存储设备中调入或调出内存， 涉及到外部存储设备，关键考虑点在于对外部存储的访问时间和访问此时。

对于树， 一个节点可以有多个孩子，但是自身只能存储一个元素。而二叉树，节点孩子树最多只有两个。 导致树的高度非常大或者树的度非常大...

多路查找树 ，每个节点孩子个数可以多于两个，并且每个节点可以存储多个元素。

2-3 树

每个节点都具有两个（2节点）或者三个孩子（3节点）。

2节点

包含一个元素和两个孩子（或者没有孩子）：

左子树小于该元素，右子树大于该元素 ；注意不同于二叉排序树，2节点要么没孩子要么2个孩子

3节点

包含一小一大2个元素和三个孩子（或者没有孩子）

一个3节点要么没孩子，要么3个孩子；

3节点有孩子：

  • 左子树小于较小元素
  • 右子树大于较大元素
  • 中间子树结语两元素之间

2-3-4 树

基于2-3树扩展

4节点包含小、中、大三个元素和四个孩子，一个4节点要么没孩子，要么有四个孩子；

左子树包含小于最小元素的元素，第二子树大于最小小于第二，第三子树大于第二小于最大，右子树大于最大。

B树

B树是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。

节点最大孩子数称为B树的阶（order）

1

2

B+ 树

why

bplus

说明:

在B树中，每个元素在树种只出现一次，有可能在分支节点，也有可能再叶子节点。而在B+树中

  • 出现在分支节点的元素会在分支的叶子节点再次出现
  • 每个叶子节点都会保存指向下个叶子节点的指针

随机查找时，从根节点出发，如果在分支节点找到关键字（只提供索引），仍需要配到达关键字所在的叶子节点

如果按从下到大顺序查找，只需沿最左侧的叶子节点，无需经过分支节点，沿着指向下一个叶子节点的指针可以遍历所有关键字

B+树的结构适合带范围的查找 - 可从根节点找到先找到下限值，然后再叶子节按顺序遍历知道上限值。

TODO

关联： mysql InnoDB B+ 索引