B树和MySql索引

1.什么是B树

它是一种平衡得多叉树,称为B树,一颗M阶的B树,是一颗平衡的M路的多叉树,可以是空树或者满足一下性质:

  • 根节点至少有两个孩子。
  • 每个节点都包含k-1个关键字和K个孩子,其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数。
  • 每个叶子节点都包含k-1个关键字,其中 ceil(m/2) ≤ k ≤ m。
  • 所有的叶子结点都在同一层,
  • 所有的节点中的关键字都是从小到大排序,节点当中k-1个元素正好是K个孩子所包含的元素的值域划分。
  • 每个结点的结构为:(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。

2.B树的插入分析

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

注意:孩子比数据多一个

3.B树插入的简单实现

#pragma once
#include <iostream>
#include <vector>
using namespace std;template<class K, size_t M = 3>
class TreeNode
{
public:TreeNode(){for (int i = 0; i < M; i++){_subs[i] = nullptr;_key[i] = K();}_subs[M] = nullptr;_parent = nullptr;_n = 0;}
public:K _key[M];TreeNode<K, M>* _subs[M + 1];TreeNode<K, M>* _parent;size_t _n;//洢
};template<class K, size_t M=3>
class BTree
{typedef TreeNode<K, M> Node;
public:pair<Node*, int> Find(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){size_t i = 0;for (i = 0; i < cur->_n; i++){if (cur->_key[i] == key){return make_pair(cur, i);}else if (cur->_key[i] > key)break;}parent = cur;cur = cur->_subs[i];}return make_pair(parent, -1);}void InsertKey(Node* parent, Node* child, const K& key){size_t end = parent->_n;while (end >= 0){if (parent->_key[end] > key){parent->_key[end + 1] = parent->_key[end];parent->_subs[end + 2] = parent->_subs[end + 1];--end;}else break;}parent->_key[end + 1] = key;parent->_subs[end + 2] = child;if (child) child->_parent = parent;parent->_n++;}bool Insert(const K& key){pair<Node*, int> ret = Find(key);if (ret.second != -1) return false;if (_root == nullptr){_root = new Node();_root->_key[0] = key;_root->_n++;return true;}Node* parent = ret.first;Node* child = nullptr;K newkey = key;while (1){InsertKey(parent, child, newkey);if (parent->_n < M) return true;else{size_t mid = parent->_n / 2;Node* brother = new Node();size_t j = 0;size_t i = mid + 1;for (i; i < M; i++){brother->_subs[j] = parent->_subs[i];brother->_key[j] = parent->_key[j];if (parent->_subs[i]){parent->_subs[i]->_parent = brother;}j++;parent->_key[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->_key[mid];parent->_key[mid] = K();if (parent->_parent == nullptr){_root = new Node();_root->_key[0] = midKey;_root->_subs[0] = parent;_root->_subs[0] = brother;_root->_n = 1;parent->_parent = _root;brother->_parent = _root;break;}else{newkey = midKey;child = brother;parent = parent->_parent;}}}return true;}void _Inorder(Node* cur){if (cur == nullptr)return;size_t i = 0;for (; i < cur->_n; ++i){_Inorder(cur->_subs[i]);    cout << cur->_key[i] << " "; }_Inorder(cur->_subs[i]);   }void Inorder(){_Inorder(_root);}private:Node* _root = nullptr;
};

4.B树,B+树B*树三者的关系

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

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

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

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

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

B*树的分裂:
当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结
点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如
果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父
结点增加新结点的指针。
所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

通过以上介绍,大致将B树,B+树,B*树总结如下:
B树:有序数组+平衡多叉树;
B+树:有序数组链表+平衡多叉树;
B*树:一棵更丰满的,空间利用率更高的B+树。

4.什么是索引

B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物,比如:
书籍目录可以让读者快速找到相关信息,hao123网页导航网站,为了让用户能够快速的找到有价
值的分类网站,本质上就是互联网页面中的索引结构。
MySQL官方对索引的定义为:索引(index)是帮助MySQL高效获取数据的数据结构,简单来说:
索引就是数据结构。
当数据量很大时,为了能够方便管理数据,提高数据查询的效率,一般都会选择将数据保存到数
据库,因此数据库不仅仅是帮助用户管理数据,而且数据库系统还维护着满足特定查找算法的数
据结构,这些数据结构以某种方式引用数据,这样就可以在这些数据结构上实现高级查找算法,
该数据结构就是索引。

索引是基于表的,而不是基于数据库的。

5.B树和索引的关系

5.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的索引方式也叫做“非聚集索引”的。

5.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域。

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2812564.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

安泰超声功率放大器技术参数有哪些

超声功率放大器是一种用于放大超声信号的设备&#xff0c;而超声功率放大器的技术参数对于设备的性能和应用场景起着重要作用。在本文中&#xff0c;我们将介绍一些常见的超声功率放大器的技术参数。 功率输出&#xff1a;超声功率放大器的功率输出是指放大器能够输出的最大功率…

【Android移动开发】Windows10平台安装Android Studio与人工智能算法模型部署案例

目录 一、Android Studio下载地址二、开发环境JDK三、开始安装Android Studio四、案例展示与搭建五、人工智能算法模型移动端部署案例参考 一、Android Studio下载地址 https://developer.android.google.cn/studio/install.html 电脑配置要求&#xff1a; 下载保存在指定文…

3.Prometheus数据模型

采样时间戳 指标 指标值平凡也就两个字: 懒和惰; 成功也就两个字: 苦和勤; 优秀也就两个字: 你和我。 跟着我从0学习JAVA、spring全家桶和linux运维等知识&#xff0c;带你从懵懂少年走向人生巅峰&#xff0c;迎娶白富美&#xff01; 关注微信公众号【 IT特靠谱 】&#xff0…

Niginx介绍和安装使用

Nginx是什么&#xff1f; Nginx (engine x) 是一个高性能的HTTP和反向代理web服务器&#xff0c;同时也提供了IMAP/POP3/SMTP服务。Nginx是由伊戈尔赛索耶夫为俄罗斯访问量第二的Rambler.ru站点&#xff08;俄文&#xff1a;Рамблер&#xff09;开发的&#xff0c;第一…

你并不了解 JavaScript:作用域与闭包 - 第二版 - 第八章:模块化模式

第八章&#xff1a;模块化模式 在本章中&#xff0c;我们将通过探索所有编程中最重要的代码组织模式之一&#xff1a;模块&#xff0c;来结束本书的正文。正如我们将看到的那样&#xff0c;模块本质上是由我们已经讲过的内容构建而成&#xff1a;这是你学习词法作用域和闭包所…

k8s(5)

目录 使用Kubeadm安装k8s集群&#xff1a; 初始化操作&#xff1a; 每台主从节点&#xff1a; 升级内核&#xff1a; 所有节点安装docker &#xff1a; 所有节点安装kubeadm&#xff0c;kubelet和kubectl&#xff1a; 修改了 kubeadm-config.yaml&#xff0c;将其传输给…

Azure Eventhub项目引入Servicebus报NoClassDefFoundError

前提 现有项目使用azure eventhub作为IOT数据载体进行数据传输。由于业务需要&#xff0c;需要同时引入servicebus。 <dependency><groupId>com.azure</groupId><artifactId>azure-messaging-servicebus</artifactId><version>7.13.3<…

springboot网站开发-使用MultipartFile上传图片文件到远程服务器

springboot网站开发-使用MultipartFile上传图片文件到远程服务器&#xff01;昨天上午在准备网站的一些 图片&#xff0c;下午在测试图片上传的模块&#xff0c;走了一些弯路&#xff0c;今天和大家分享一下&#xff0c;免得大家再走弯路。 首先&#xff0c;要和大家声明一件事…

vue3使用echarts绘制地图

vue3使用echarts绘制地图 安装echarts npm install echarts下载地图的json数据【我这里是把json数据单独粘出来然后新建了一个文件china.json】 下载中国及各个省份的地图数据引入 import chinaJson from ./china.json绘制地图 <template><div ref"myChart&q…

面试经典150题【31-40】

文章目录 面试经典150题【31-40】76.最小覆盖字串36.有效的数独54.螺旋矩阵48.旋转图像73.矩阵置零289.生命游戏383.赎金信205.同构字符串290.单词规律242.有效的字母异位词 面试经典150题【31-40】 76.最小覆盖字串 基本思路很简单&#xff0c;就是先移动右边到合适位置。再移…

网络安全与IP安全网络安全

网络安全与IP安全网络安全 网络安全 是指网络系统的硬件&#xff0c;软件以及系统中的数据收到的保护。 保护的基本属性为&#xff1a;机密性&#xff0c;身份认证&#xff0c;完整性和可用性&#xff1b; 基本特征&#xff1a;相对性&#xff0c;时效性&#xff0c;相关性…

[面试]我们常说的负载均衡是什么东西?

什么是负载均衡 如果用户量很多, 服务器的流量也随之增大, 此时出现两个问题, 软件性能下降 容易出现单点故障 为了解决这些问题, 引入了集群化架构, 也就是把一个软件同时部署在多个服务器上 集群化架构出现的问题 架构改变后又出现了两个问题 如何将请求均匀的发送到多…

大疆无人机视频删了怎么恢复?尝试这些恢复技巧

无人机拍摄的视频已经成为许多飞行爱好者和专业人士珍贵的记忆与资料。然而&#xff0c;误删视频是许多人都可能遇到的问题。当您不慎删除了大疆无人机中的视频时&#xff0c;不必过于焦虑。本文将为您详细介绍如何恢复这些误删的视频&#xff0c;帮助您找回宝贵的回忆。 图片来…

Laravel03 路由到控制器与连接数据库

Laravel03 路由到控制器与连接数据库 1. 路由到控制器2. 连接数据库 1. 路由到控制器 如下图一些简单的逻辑处理可以放在web.php中&#xff0c;也就是路由的闭包函数里面。但是大的项目&#xff0c;我们肯定不能这么写。 为什么保证业务清晰好管理&#xff0c;都应该吧业务逻辑…

【Linux深入剖析】进程优先级 | 命令行参数 | 环境变量

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 目录 1.进程优先级2.Linux…

[C++]使用C++实现监控文件是否被修改

软件开发过程中经常会用到配置文件,某些应用场景要求在软件运行时动态修改配置文件,此时就需要监控配置文件是否被修改,下面我们就来看看如何使用C实现这一功能吧 软件开发过程中经常会用到配置文件&#xff0c;某些应用场景要求在软件运行时动态修改配置文件&#xff0c;此时…

国产服务器操作系统

为何记录 最近的开发工作经常接触到国产服务器操作系统的业务&#xff0c;经常被x86、arm、龙芯、鲲鹏、欧拉...搞得一脸懵逼&#xff0c;遂记之&#xff01; 操作系统 这里按照应用场景分&#xff1a; 桌面操作系统&#xff1a;主要用于pc&#xff0c;如Windows、macOS、Li…

MES系统生产订单管理:多角度全面解析

一、MES系统生产订单管理概述 MES中的生产订单管理涉及到订单的接收、处理、执行和跟踪等多个方面。MES系统生产订单管理旨在确保生产过程中的订单信息准确无误、生产进度可控&#xff0c;从而实现高效、有序的生产。 二、生产订单管理的核心功能 订单接收与处理&#xff1a;…

30-k8s集群的七层代理-ingress资源(进阶知识)

一、ingress概述 1&#xff0c;引发问题 目前使用svc资源做网络暴露&#xff0c;使用nodeport类型&#xff0c;一个业务对应一个宿主机端口&#xff0c;那么如果业务多了&#xff0c;所占用的宿主机端口也就多了&#xff0c;虽然说宿主机端口一般情况下都是够用的&#xff0c;…

Android Jni的介绍和简单Demo实现

Android Jni的介绍和简单Demo实现 文章目录 Android Jni的介绍和简单Demo实现一、JNI的简单介绍JNINDKJni的开发背景&#xff1a;**JNI在 Android 开发里的主要应用场景&#xff1a;** 二、JNI的简单Demo1、Demo主要界面和效果展示2、CMake编译加载文件add_library 指令的加载库…