数据结构B树或者B+树怎么构造 求告知

一、B树的起源

B树，最早是由德国计算机科学家Rudolf Bayer等人于1972年在论文 《Organization and Maintenance of Large Ordered Indexes》提出的，不过我去看了看原文，发现作者也没有解释为什么就叫B-trees了，所以把B树的B，简单地解释为Balanced或者Binary都不是特别严谨，也许作者就是取其名字Bayer的首字母命名的也说不定啊……

二、B树长啥样

还是直接看图比较清楚，图中所示，B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉（m>=2），我们称之为m阶b树，为了体现本博客的良心之处，不同于其他地方都能看到2阶B树，这里特意画了一棵5阶B树 。

总的来说，m阶B树满足以下条件：

每个节点至多可以拥有m棵子树

根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)

非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)

非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki<Ki+1，A为指向子树根节点的指针

从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空

B树的查询过程和二叉排序树比较类似，从根节点依次比较每个结点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针

例如查询图中字母表中的K

从根节点P开始，K的位置在P之前，进入左侧指针

左子树中，依次比较C、F、J、M，发现K在J和M之间

沿着J和M之间的指针，继续访问子树，并依次进行比较，发现第一个关键字K即为指定查找的值

三、Plus版——B+树

作为B树的加强版，B+树与B树的差异在于：

有n棵子树的节点含有n个关键字（也有认为是n-1个关键字）

所有的叶子节点包含了全部的关键字，及指向含这些关键字记录的指针，且叶子节点本身根据关键字自小而大顺序连接

非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字

请点击输入图片描述

B+树的查找过程，与B树类似，只不过查找时，如果在非叶子节点上的关键字等于给定值，并不终止，而是继续沿着指针直到叶子节点位置。因此在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径

一个 B-Tree 是一种针对在块设备上优化 *** 作的数据结构。块设备或磁盘有相当重要的数据访问延迟，尤其是机械硬盘。在随机位置检索单个字节并不比检索更大的数据花费的时间更少。这是 B-Tree 的基本原理，InnoDB 使用的数据页为 16KB。让我们尝试简化 B-Tree 的描述。B-Tree 是围绕这键来组织的数据结构。键用于搜索 B-Tree 内的数据。B-Tree 通常有多个级别。数据仅存储在最底层，即叶子节点。其他级别的页面（节点）仅包含下一级别的页面的键和指针。如果要访问键值的数据，则从顶级节点-根节点开始，将其包含的键与搜索值进行比较，并找到要在下一级访问的页面。重复这个过程，直到你达到最后一个级别，即叶子节点。理论上，每个 B-Tree 级别的读取都需要一次磁盘读取 *** 作。在实践中，总是有内存缓存节点，因为它们数量较少且经常访问，因此适合缓存。一个简单的三级 B-Tree 结构

这时我们需要：

1、定位到记录所在的页

2、从页内查找相应的记录

在前面我们知道了为了主键快速一条记录在页中的位置而设立页目录，类似的办法，为了定位一条记录在所在的数据页我们也可以建立一个别的目录，在建立这个目录的过程中，我们必须做2件事情：

上文叙述的目录项和用户记录长得挺像，只不过目录项中的两个列是主键和页号。所以，我们可以直接复用之前的数据页来存储目录项。采用 record_type 字段区分普通的记录

同时，目录项的 min_rec_flag 为1，普通记录都为0

上面的数据结构就是B+树，真正用来存放用户记录的都是B+树最底层的叶子节点，其余用来存放目录项记录的节点称为非叶子节点或者内节点，最上边的节点称为根节点。

这里我们假设一个数据页，只能存3条记录，实际上一个页可以存很多条记录。假设一个数据页可以存100条用户记录，1000条目录项记录，那么：

如果B+树只有1层，则最多存放 100 条用户记录

如果B+树只有2层，则最多能存放 1000 * 100 =

如果B+树只有3层，则最多能存放 1000 * 1000 * 100 =

如果B+树只有4层，则最多能存放 1000 * 1000 * 1000 * 100 =

所以，我们一般用到的B+树不会超过4层，也就意味着通过主键查找记录时，最多只需要进行4个页面的查找就可以找到。

InnoDB 会自动为主键或者带有 UNIQUE 属性的列建立索引。

KEY 和 INDEX 是同义词，创建索引命名时以 idx 为前缀，后面跟着需要建立索引的列名，且多个列名之间用下划线隔开。

也可以在修改表结构的时候添加索引

最后，删除这个索引。

---