数据结构——B树和B+树

数据结构——B树和B+树

• 一、B树
• • 1.B树的特征
  • 2.B树的插入操作
  • 3.B树的删除操作
  • 4.B树的缺点
  • 二、B+树
  • • B+���的特征

      平衡二叉树或红黑树的查找效率最高，时间复杂度是O(nlogn)。但不适合用来做数据库的索引树。

      因为磁盘和内存读写速度有明显的差距，磁盘中存储的数据需要先读取到内存中才能进行高速的检索。而数据库当中存储着海量的数据，光是数据库索引就有可能占据几个GB甚至更大的空间。当我们要查找数据的时候，显然不可能把整个索引树读到内存中。因此，我们只能以索引树的节点为基本单元，每次把单一节点从磁盘读取到内存当中，进行后续操作。

      如果磁盘当中的索引树是一棵平衡二叉树，查找的时候，在最坏情况下，磁盘I/O的次数等于索引树的高度。

      为了减少磁盘I/O，我们需要把原本“瘦高”的树结构变得“矮胖”，让每一个节点承载更多的元素，拥有更多的孩子。

      B树和B+树，就是这样的数据结构，因此它们非常适合做数据库和文件系统的索引。

      一、B树

      1.B树的特征

      B树也被称为B-树（中间的横线是一个连接符，不是“B减树”！）

      B树单一节点拥有的最多子节点数量，称为B树的“阶”。一个m阶的B树，具有如下几个特征：

      1. 根节点至少有两个子节点。
      2. 每个中间节点都包含k-1个元素（也被称为关键字）和k个孩子，其中m/2