数据结构之B树、B+树、B*树

2021年5月3日 13点热度 0条评论 来源: 冰河winner

1、应用背景

二叉查找树、AVL树、红黑树等都属于二叉树的范围,查找的时间复杂度是O(log 2N),与树的深度相关,那么降低树的深度自然会提高查找效率。
但是我们面对这样一个实际问题:大规模数据存储中,树节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下。
因此,为了减少磁盘I/O的次数,必须降低树的深度,将“瘦高”的树变得“矮胖”。一个基本的想法就是:

  • 每个节点存储多个元素
  • 摒弃二叉树结构,采用多叉树

这样就引出来了一个新的查找树结构 ——多路查找树。根据AVL树给我们的启发,一颗平衡多路查找树可以使得数据的查找效率保证在O(logN)这样的对数级别上。

1.1 机械硬盘结构

为什么树的深度会与磁盘I/O相关呢?这要从硬件层面来说明。
机械硬盘的结构图如下:

硬盘中一般会有多个盘片组成,每个盘片包含两个面,每个盘面都对应地有一个读/写磁头。
每个盘面都被划分为数目相等的磁道,并从外缘的“0”开始编号,具有相

    原文作者:冰河winner
    原文地址: https://blog.csdn.net/u012152619/article/details/84669668
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。