数据结构——B-树

Ne0inhk

— 18 min read
数据结构——B-树

目录

一.常见的搜索结构

二.B-树概念

三.B-树的插入分析及实现

1.插入分析

2.插入实现

1. B-树的节点设计

2.插入key的过程

3.B-树的插入实现

4.B-树的验证

5.B-树的性能分析

四.B+树和B*树

1.B+树

2.B*树

3.总结

五.B-树的应用

1.索引

2.MySQL索引简介

1.MyISAM

2.InnoDB

六.整体代码

1.BTree.h

2.test.cpp

一.常见的搜索结构

        以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘上，有需要搜索某些数据，那么如果处理呢？那么我们可以考虑将存放关键字及其映射的数据的 地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据

使用平衡二叉树搜索树的缺陷：

        平衡二叉树搜索树的高度是logN，这个查找次数在内存中是很快的。但是当数据都在磁盘中时， 访问磁盘速度很慢，在数据量很大时，logN次的磁盘访问，是一个难以接受的结果

使用哈希表的缺陷:

        哈希表的效率很高是O(1)，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难以接受的

那如何加速对数据的访问呢？

  1. 提高IO的速度(SSD相比传统机械硬盘快了不少，但是还是没有得到本质性的提升)
  2. 降低树的高度---多叉树平衡树

二.B-树概念

        1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树 (后面有一个B的改进版本B+树，然后有些地方的B树写的的是B-树，注意不要误读成"B减树")。一棵m阶(m>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足以下性质：

  1. 根节点至少有两个孩子
  2. 每个分支节点都包含k-1个关键字和k个孩子，其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数
  3. 每个叶子节点都包含k-1个关键字，其中 ceil(m/2) ≤ k ≤ m
  4. 所有的叶子节点都在同一层
  5. 每个节点中的关键字从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划 分
  6. 每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An）其中，Ki(1≤i≤n)为关键 字，且Ki<Ki+1(1<=i<=n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的 关键字均小于Ki+1,n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1

三.B-树的插入分析及实现

1.插入分析

        为了简单起见，假设M = 3. 即三叉树，每个节点中存储两个数据，两个数据可以将区间分割成三个部分，因此节点应该有三个孩子，为了后续实现简单期间，节点的结构如下

        注意：孩子永远比数据多一个

        用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：

 pair<Node*, int> Find(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { size_t i = 0; while (i < cur->_n) { if (key < cur->_keys[i]) { break; } else if (key > cur->_keys[i]) { ++i; } else { return make_pair(cur, i); } } parent = cur; cur = cur->_subs[i]; } return make_pair(parent, -1); }

插入总结:

  1. 如果树为空，直接插入新节点中，该节点为树的根节点
  2. 树非空，找待插入元素在树中的插入位置(注意：找到的插入节点位置一定在叶子节点中)
  3. 检测是否找到插入位置(假设树中的key唯一，即该元素已经存在时则不插入)
  4. 按照插入排序的思想将该元素插入到找到的节点中
  5. 检测该节点是否满足B-树的性质：即该节点中的元素个数是否等于M，如果小于则满足
  6. 如果插入后节点不满足B树的性质，需要对该节点进行分裂：
    1. 申请新节点
    2. 找到该节点的中间位置
    3. 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
    4. 将中间位置元素以及新节点往该节点的双亲节点中插入，即继续4
  7. 如果向上已经分裂到根节点的位置，插入结束

2.插入实现

1. B-树的节点设计

template<class K,size_t M> struct BTreeNode { //为了方便插入后分裂,多开一个空间 K _keys[M]; BTreeNode<K, M>* _subs[M + 1]; BTreeNode<K, M>* _parent; size_t _n;//记录实际存储多少个关键字 BTreeNode() { for (size_t i = 0; i < M; ++i) { _keys[i] = K(); _subs[i] = nullptr; } _subs[M] = nullptr; _parent = nullptr; _n = 0; } };

2.插入key的过程

void InsertKey(Node* node, const K& key, Node* child) { int end = node->_n - 1; while (end >= 0) { if (key < node->_keys[end]) { node->_keys[end + 1] = node->_keys[end]; node->_subs[end + 2] = node->_subs[end + 1]; --end; } else { break; } } node->_keys[end + 1] = key; node->_subs[end + 2] = child; if (child) { child->_parent = node; } node->_n++; }

3.B-树的插入实现

bool Insert(const K& key) { if (_root == nullptr) { _root = new Node; _root->_keys[0] = key; _root->_n++; return true; } pair<Node*, int> ret = Find(key); if (ret.second >= 0) { return false; } Node* parent = ret.first; K newkey = key; Node* child = nullptr; while (1) { InsertKey(parent, newkey, child); //满了就分裂,没有满插入结束 if (parent->_n < M) { return true; } else { size_t mid = M / 2; //分裂一半[mid + 1, M - 1]给兄弟 Node* brother = new Node; size_t j = 0; size_t i = mid + 1; for( ; i <= M - 1; ++i) { brother->_keys[j] = parent->_keys[i]; brother->_subs[j] = parent->_subs[i]; if (parent->_subs[i]) { parent->_subs[i]->_parent = brother; } ++j; parent->_keys[i] = K(); parent->_subs[i] = nullptr; } brother->_subs[j] = parent->_subs[i]; if (parent->_subs[i]) { parent->_subs[i]->_parent = brother; } parent->_subs[i] = nullptr; brother->_n = j; parent->_n -= (brother->_n + 1); K midkey = parent->_keys[mid]; parent->_keys[mid] = K(); if (parent->_parent == nullptr) { _root = new Node; _root->_keys[0] = midkey; _root->_subs[0] = parent; _root->_subs[1] = brother; _root->_n = 1; parent->_parent = _root; brother->_parent = _root; break; } else { newkey = midkey; child = brother; parent = parent->_parent; } } } return true; }

4.B-树的验证

        对B树进行中序遍历，如果能得到一个有序的序列，说明插入正确

//左根 左根 ......右 void _InOrder(Node* root) { if (root == nullptr) return; size_t i = 0; for (; i < root->_n; ++i) { _InOrder(root->_subs[i]);//左子树 cout << root->_keys[i] << " ";//根 } _InOrder(root->_subs[i]);//最后的右子树 } void InOrder() { _InOrder(_root); }

5.B-树的性能分析

        对于一棵节点为N度为M的B-树，查找和插入需要

$log_{M-1}N$

和

$log_{M/2}N$

次比较，这个很好证明：对于度为M的B-树，每一个节点的子节点个数为M/2 ~(M-1)之间，因此树的高度应该在要

$log_{M-1}N$

和

$log_{M/2}N$

之间，在定位到该节点后，再采用二分查找的方式可以很快的定位到该元素

        B-树的效率是很高的，对于N = 62*1000000000个节点，如果度M为1024，则

$log_{M/2}N$

，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数

四.B+树和B*树

1.B+树

        B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：

  1. 分支节点的子树指针与关键字个数相同
  2. 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
  3. 所有叶子节点增加一个链接指针链接在一起
  4. 所有关键字及其映射数据都在叶子节点出现

B+树的特性:

  1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的
  2. 不可能在分支节点中命中
  3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层

2.B*树

        B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针

        B+树的分裂:

        当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针

        B*树的分裂:

        当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针

        所以，B*树分配新结点的概率比B+树要低，空间使用率更高

3.总结

通过以上介绍，大致将B树，B+树，B*树总结如下：

  1. B树：有序数组+平衡多叉树
  2. B+树：有序数组链表+平衡多叉树
  3. B*树：一棵更丰满的，空间利用率更高的B+树

五.B-树的应用

1.索引

        B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物，比如： 书籍目录可以让读者快速找到相关信息，hao123网页导航网站，为了让用户能够快速的找到有价值的分类网站，本质上就是互联网页面中的索引结构

        MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说： 索引就是数据结构

        当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法， 该数据结构就是索引

2.MySQL索引简介

        mysql是目前非常流行的开源关系型数据库，不仅是免费的，可靠性高，速度也比较快，而且拥有灵活的插件式存储引擎，如下：

        MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的

        注意：索引是基于表的，而不是基于数据库的

1.MyISAM

        MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事物，支持全文检索，使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，其结构如下：

        上图是以以Col1为主键，MyISAM的示意图，可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索 引要求key是唯一的，而辅助索引的key可以重复。如果想在Col2上建立一个辅助索引，则此索引 的结构如下图所示：

        同样也是一棵B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”

2.InnoDB

        InnoDB存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从MySQL数据库5.5.8版 本开始，InnoDB存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但 InnoDB使用B+Tree作为索引结构时，具体实现方式却与MyISAM截然不同

        第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的， 索引文件仅保存数据记录的地址。而InnoDB索引，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此 InnoDB表数据文件本身就是主索引

        上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录， 这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数 据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主 键，这个字段长度为6个字节，类型为长整型

        第二个区别是InnoDB的辅助索引data域存储相应记录主键的值而不是地址,所有辅助索引都引用主键作为data域

        聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录

六.整体代码

1.BTree.h

#pragma once template<class K,size_t M> struct BTreeNode { //为了方便插入后分裂,多开一个空间 K _keys[M]; BTreeNode<K, M>* _subs[M + 1]; BTreeNode<K, M>* _parent; size_t _n;//记录实际存储多少个关键字 BTreeNode() { for (size_t i = 0; i < M; ++i) { _keys[i] = K(); _subs[i] = nullptr; } _subs[M] = nullptr; _parent = nullptr; _n = 0; } }; template<class K,size_t M> class BTree { typedef BTreeNode<K, M> Node; public: pair<Node*, int> Find(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { size_t i = 0; while (i < cur->_n) { if (key < cur->_keys[i]) { break; } else if (key > cur->_keys[i]) { ++i; } else { return make_pair(cur, i); } } parent = cur; cur = cur->_subs[i]; } return make_pair(parent, -1); } void InsertKey(Node* node, const K& key, Node* child) { int end = node->_n - 1; while (end >= 0) { if (key < node->_keys[end]) { node->_keys[end + 1] = node->_keys[end]; node->_subs[end + 2] = node->_subs[end + 1]; --end; } else { break; } } node->_keys[end + 1] = key; node->_subs[end + 2] = child; if (child) { child->_parent = node; } node->_n++; } bool Insert(const K& key) { if (_root == nullptr) { _root = new Node; _root->_keys[0] = key; _root->_n++; return true; } pair<Node*, int> ret = Find(key); if (ret.second >= 0) { return false; } Node* parent = ret.first; K newkey = key; Node* child = nullptr; while (1) { InsertKey(parent, newkey, child); //满了就分裂,没有满插入结束 if (parent->_n < M) { return true; } else { size_t mid = M / 2; //分裂一半[mid + 1, M - 1]给兄弟 Node* brother = new Node; size_t j = 0; size_t i = mid + 1; for( ; i <= M - 1; ++i) { brother->_keys[j] = parent->_keys[i]; brother->_subs[j] = parent->_subs[i]; if (parent->_subs[i]) { parent->_subs[i]->_parent = brother; } ++j; parent->_keys[i] = K(); parent->_subs[i] = nullptr; } brother->_subs[j] = parent->_subs[i]; if (parent->_subs[i]) { parent->_subs[i]->_parent = brother; } parent->_subs[i] = nullptr; brother->_n = j; parent->_n -= (brother->_n + 1); K midkey = parent->_keys[mid]; parent->_keys[mid] = K(); if (parent->_parent == nullptr) { _root = new Node; _root->_keys[0] = midkey; _root->_subs[0] = parent; _root->_subs[1] = brother; _root->_n = 1; parent->_parent = _root; brother->_parent = _root; break; } else { newkey = midkey; child = brother; parent = parent->_parent; } } } return true; } //左根 左根 ......右 void _InOrder(Node* root) { if (root == nullptr) return; size_t i = 0; for (; i < root->_n; ++i) { _InOrder(root->_subs[i]);//左子树 cout << root->_keys[i] << " ";//根 } _InOrder(root->_subs[i]);//最后的右子树 } void InOrder() { _InOrder(_root); } private: Node* _root = nullptr; }; void TestBTree() { int a[] = { 53,139,75,49,145,36,101 }; BTree<int, 3> t; for (auto e : a) { t.Insert(e); } t.InOrder(); }

2.test.cpp

#include<iostream> using namespace std; #include"BTree.h" int main() { TestBTree(); }

Read more

DeepFace深度学习库+OpenCV实现——情绪分析器

DeepFace深度学习库+OpenCV实现——情绪分析器

目录 应用场景 实现组件 1. 硬件组件 2. 软件库与依赖 3. 功能模块 代码详解（实现思路） 导入必要的库 打开摄像头并初始化变量 主循环 FPS计算 情绪分析及结果展示 显示FPS和图像 退出条件 编辑 完整代码 效果展示 自然的 开心的 伤心的 恐惧的 惊讶的  效果展示 自然的 开心的 伤心的 恐惧的 惊讶的   应用场景         应用场景比较广泛，尤其是在需要了解和分析人类情感反应的场合。： 1. 心理健康评估：在心理健康领域，可以通过长期监控和分析一个人的情绪变化来辅助医生进行诊断或治疗效果评估。 2. 用户体验研究：在产品设计、广告制作或网站开发过程中，通过观察用户在使用过程中的情绪反应，来优化产品的用户体验。 3. 互动娱乐：在游戏或虚拟现实应用中，根据玩家的情绪状态动态调整游戏难度或故事情节，以增加沉浸感和互动性。

By Ne0inhk
最全java面试题及答案（208道）

最全java面试题及答案（208道）

本文分为十九个模块，分别是：「Java 基础、容器、多线程、反射、对象拷贝、Java Web 、异常、网络、设计模式、Spring/Spring MVC、Spring Boot/Spring Cloud、Hibernate、MyBatis、RabbitMQ、Kafka、Zookeeper、MySQL、Redis、JVM」 ，如下图所示： 共包含 208 道面试题，本文的宗旨是为读者朋友们整理一份详实而又权威的面试清单，下面一起进入主题吧。 Java 基础 1. JDK 和 JRE 有什么区别？ * JDK：Java Development Kit 的简称，Java 开发工具包，提供了 Java

By Ne0inhk
用 DeepSeek 打造你的超强代码助手

用 DeepSeek 打造你的超强代码助手

DeepSeek Engineer 是啥？ 简单来说，DeepSeek Engineer 是一个基于命令行的智能助手。它能帮你完成这些事： * 快速读文件内容：比如你有个配置文件，直接用命令把它加载进助手，后续所有操作都可以基于这个文件。 * 自动改文件：它不仅能提建议，还可以直接生成差异表（diff），甚至自动应用修改。 * 智能代码生成：比如你让它生成代码片段，它会按照指定格式和规则直接返回。 更重要的是，这一切都是通过 DeepSeek 的强大 API 来实现的。想象一下，你有个贴身助手，不仅能听懂你的代码需求，还能直接动手帮你写！ 核心功能拆解 我们先来看 DeepSeek Engineer 的几个核心能力，让你更好地理解它的强大之处。 1. 自动配置 DeepSeek 客户端 启动这个工具时，你只需要准备一个 .env 文件，里面写上你的 API Key，比如： DEEPSEEK_API_

By Ne0inhk
10分钟打造专属AI助手！ToDesk云电脑/顺网云/海马云操作DeepSeek哪家强？

10分钟打造专属AI助手！ToDesk云电脑/顺网云/海马云操作DeepSeek哪家强？

文章目录 * 一、引言 * 云计算平台概览 * ToDesk云电脑：随时随地用上高性能电脑 * 二 .云电脑初体验 * DeekSeek介绍 * 版本参数与特点 * 任务类型表现 * 1、ToDesk云电脑 * 2、顺网云电脑 * 3、海马云电脑 * 三、DeekSeek本地化实操和AIGC应用 * 1. ToDesk云电脑 * 2. 海马云电脑 * 3、顺网云电脑 * 四、结语 * 总结：云电脑如何选择？ 一、引言 DeepSeek这些大模型让 AI 开发变得越来越有趣，但真要跑起来，可没那么简单！ * 本地配置太麻烦：显卡不够、驱动难装、环境冲突，光是折腾这些就让人心态崩了。 * 云端性能参差不齐：选错云电脑，可能卡到爆、加载慢，还容易掉线，搞得效率直线下降。 * 成本难控：有的平台按小时计费，价格一会儿一个样，

By Ne0inhk