0%

《数据结构与算法》BTree 平衡多路查找树

BTree 是为磁盘等外存储设备设计的一种平衡查找树

BTree 分为 B-Tree 和 B+Tree

B-Tree

平衡二叉搜索树

平衡二叉搜索树的查找次数(类比于磁盘 IO)取决于树的高度,所以要压缩高度,由此衍生出了多路平衡搜索树 B-tree

就是一个节点中有多个 key

例子查找 60

  1. 根据根节点找到磁盘块 1,读入内存。【磁盘 I/O 操作第 1 次】
  2. 比较关键字 60 大于区间(17,35),找到磁盘块 1 的指针 P3。
  3. 根据 P3 指针找到磁盘块 4,读入内存。【磁盘 I/O 操作第 2 次】
  4. 比较关键字 60 小于在区间(65,87),找到磁盘块 3 的指针 P1。
  5. 根据 P2 指针找到磁盘块 9,读入内存。【磁盘 I/O 操作第 3 次】
  6. 在磁盘块 9 中的关键字列表中找到关键字 60。

分析上面过程,发现需要 3 次磁盘 I/O 操作,和 3 次内存查找操作。

由于内存中的关键字是一个有序表结构,可以利用二分法查找提高效率。

而3次磁盘 I/O 操作是影响整个 B-Tree 查找效率的决定因素。

B-Tree 使每次磁盘 I/O 取到内存的数据都发挥了作用,从而提高了查询效率。

B+Tree

B-Tree 结构图中可以看到每个节点中不仅包含数据的 key 值,还有 data 值。

而每一个页的存储空间是有限的,如果 data 数据较大时将会导致每个节点(即一个页)能存储的 key 的数量很小,当存储的数据量很大时就会导致 B-Tree 的深度较大,就会增大查询时的磁盘 I/O 次数,进而影响查询效率。

在 B+Tree 中,所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上,而非叶子节点上只存储 key 值信息,这样可以大大加大每个节点存储的 key 值数量,降低 B+Tree 的高度。

通常在 B+Tree 上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点,而且所有叶子节点(即数据节点)之间是一种首尾相连的链式环结构。

而 B-Tree 的节点之间没有首尾相连,当在做范围查询时,无法通过某个数据节点直接顺序读写找到下一个数据节点(区中的页是物理连续的,页中的行也是物理连续的),只能通过随机读写得到,相比 B+Tree 大大降低了查询效率




微信关注我,及时接收最新技术文章