本文共 1291 字,大约阅读时间需要 4 分钟。
B+树索引是数据库中最常见且应用最广泛的索引结构之一。它是从平衡二叉树(AVL Tree)和平衡多路查找树(B-Tree)演化而来的,具有更高的效率和更强的适用性。
二叉树是数据存储的基础结构,二叉查找树(Binary Search Tree,BST)要求左子树所有键值小于根节点键值,右子树所有键值大于根节点键值。其查找效率较低,因为当树深度较大时,查找次数会显著增加。
例如,以下二叉树的查找效率较低:
3 / \ 1 4 / \ / \2 3 5 6
深度为3的节点查找次数为3,平均查找次数约为2.3次。
为了提高查找效率,需要引入平衡二叉树。
平衡二叉树(AVL Tree)是二叉查找树的升级版,确保任意节点的左、右子树高度差不超过1。其失去平衡时会出现四种姿态:LL、RR、LR、RL,需要通过旋转恢复平衡。
AVL树的优点:
失去平衡后的旋转方法:
旋转示意图:
3 / \ 1 4 / \ / \2 3 5 6
旋转后树的高度降低,查找效率提升。
B-Tree是为磁盘存储设计的平衡树,优化了B+树的结构。其特点:
B-Tree的节点结构:
查找关键字29的过程:
总磁盘I/O操作次数:3次
B-Tree的优点:
B+树在B-Tree基础上进一步优化:
优化后,每个节点存储更多键值,减少磁盘深度,提升查询效率。
B+树的特点:
常见应用:
InnoDB存储引擎中,B+树的高度通常在2至4层,根节点常驻内存,查询效率高。
从二叉树到B+树,索引结构不断演化以适应存储需求。B+树通过优化节点结构和查询路径,显著提升了数据库查询效率,成为数据库索引的核心技术。
转载地址:http://xsbfk.baihongyu.com/