对B-树的理解
目录
- 前言-为什么要使用B-树?
- B-树概念
前言-为什么要使用B-树?
首先,我们正常的搜索都有一下方式:
- 搜索二叉树,极端场景下会退化,类似于单支,此时的效率变成了O(N);
- 为了解决1的问题,提出了平衡树的概念,左右子树的高度差不大于1,AVL树,红黑树。该效率为O(logN),其中map/set就是由此构建的;
- 更好的搜索结构则有哈希/散列表,该效率为O(1),–unordered_map/unordered_set
- 跳表、字典树
上面的结构都是完成内存中数据的搜索查找问题
但假设此时的数据量很多,在内存中存放不下,数据要存到磁盘中,上面的数据结构就不好了,虽然可以把内存在磁盘的地址使用AVL树来存储,查找的时间复杂度为O(logN),但是该复杂度在内存中访问非常快,在磁盘中,logN次磁盘IO访问会非常慢。 如果换成哈希表,变成O(1),在极端情况下,哈希表冲突十分厉害,一个桶中数据太多,会影响效率,并且哈希表中存在很多附带数据(表结构、节点中的指针等),数据量很大时,内存占用很多。B树则能解决这些问题。
B-树概念
B树是一种平衡的多叉树,一颗M阶(M>2)的B树,为平衡的M路平衡搜索树,可以是空树或者满足以下性质:
- 根节点至少有两个孩子
- 每个非根节点至少有M/2(向上取整)个孩子,至多有M个孩子
- 每个非根节点至少有M/2-1(向上取整)个关键字,至多有M-1个关键字,并且以升序排列
- key(1)和key(i+1)之间的孩子节点的值介于key[i]、key[i+1]之间
- 所有的叶子节点都在同一层
对上述性质进行总结来说:
根节点:关键字数量[1,M-1],孩子数量[2,M]
非根节点:关键字数量[M/2-1, M-1],孩子数量[M/2,M]
每个节点中,孩子的数量比关键字的数量永远要多一个
那么为什么会有这样的性质呢?结合例子来进行理解
针对根节点的数量范围分析:
首先,一个关键字会有两个孩子(左孩子和右孩子),其中和相邻的关键字会共有一个孩子,即关键字1的右孩子也是关键字2的左孩子,那么孩子的数量就会比关键字的数量多一个。
针对非根节点的数量范围分析:
假设M等于3,那么根节点的关键字数量最多只能放2个,如果放到了3个,则违反了规则,根节点最多存M-1个关键字,那么就会进行分裂,创建一个兄弟节点,右边M/2的值拷贝到兄弟节点中,中间值插入到父亲,如果没有父亲,则创建新的父亲,该值作为新的根。也就是上图右下角的节点,关键字70超出范围,则进行分裂,将70分裂为兄弟节点,50插入到父亲节点。
那么为什么分裂的时候要提中位数插入到父亲呢?
因为分裂新增一个兄弟节点,对于父亲而言,多了一个孩子,还得多一个关键字,这样才能保持孩子的数量比关键字数量多一个。
结合分裂的思想:
如果M是奇数,分裂时两边数量为M/2,中间值插入到父亲。(比如M=9,左右各为4,剩余的一个节点插入到父亲,如果没有父亲则创建)
如果M是偶数,因为两边要有一个需要插入到父亲,因此总有一边要少一个,一边是M/2,一边是M/2-1。(比如M=10,左右为5和4或者4和5,剩余一个插入到父亲,如果没有父亲则创建)
上一篇: php str_rot13 函数用于获取字符串的 ROT13 编码
下一篇: 语法03
推荐阅读
-
我对软件工程的理解
-
14-傅里叶变换的代码实现-一、numpy实现傅里叶变换和逆傅里叶变换 1.numpy实现傅里叶变换numpy.fft.fft2实现傅里叶变换,返回一个复数数组(complex ndarray),也就是频谱图像numpy.fft.fftshift将零频率分量移到频谱中心(将左上角的低频区域,移到中心位置) 20*np.log(np.abs(fshift))设置频谱的范围。可以理解为,之前通过傅里叶变换得到复数的数组,是不能通过图像的方法展示出来的,需要转换为灰度图像(映射到[0,255]区间)需要注意的是1> 傅里叶得到低频、高频信息,针对低频、高频处理能够实现不同的目的2> 傅里叶过程是可逆的,图像经过傅里叶变换、逆傅里叶变换后,能够恢复到原始图像3> 在频域对图像进行处理,在频域的处理会反映在逆变换图像上 # 将绘制的图显示在窗口 %matplotlib qt5 import cv2 import numpy as np import matplotlib.pyplot as plt img = cv2.imread(r"image\lena.bmp",cv2.IMREAD_GRAYSCALE) # 傅里叶变换 f = np.fft.fft2(img) # 移动中心位置 fshift = np.fft.fftshift(f) # 调整值范围 result = 20*np.log(np.abs(fshift)) plt.subplot(1,2,1) plt.imshow(img,cmap=plt.cm.gray) plt.title("original") plt.axis("off") plt.subplot(1,2,2) plt.imshow(result,cmap=plt.cm.gray) plt.title("result") plt.axis("off") plt.show 傅里叶变换的频谱图像: 2.numpy实现逆傅里叶变换numpy.fft.ifft2实现逆傅里叶变换,返回一个复数数组(complex ndarray)numpy.fft.ifftshiftfftshift函数的逆函数,将中心位置的低频,重新移到左上角iimg = np.abs(逆傅里叶变化结果)设置值的范围,映射到[0,255]区间 # 将绘制的图显示在窗口 %matplotlib qt5 import cv2 import numpy as np import matplotlib.pyplot as plt img = cv2.imread(r"image\boat.bmp",cv2.IMREAD_GRAYSCALE) # 傅里叶变换 f = np.fft.fft2(img) fshift = np.fft.fftshift(f) # 逆傅里叶变换 ishift = np.fft.ifftshift(fshift) iimg = np.fft.ifft2(ishift) iimg = np.abs(iimg) plt.subplot(1,2,1) plt.imshow(img,cmap=plt.cm.gray) plt.title("original") plt.axis("off") plt.subplot(1,2,2) plt.imshow(iimg,cmap=plt.cm.gray) plt.title("iimg") plt.axis("off") plt.show 将一副图像,进行傅里叶变换和逆傅里叶变换后,进行对比(一样的) 实例:通过numpy实现高通滤波,保留图像的边缘信息 获取图像的形状rows,cols = img.shape获取图像的中心点crow,ccol = int(rows/2),int(cols/2)将频谱图像的中心区域(低频区域)设置为0(黑色)fshift[crow-30:crow+30,ccol-30:ccol+30] = 0 # 将绘制的图显示在窗口 %matplotlib qt5 import cv2 import numpy as np import matplotlib.pyplot as plt img = cv2.imread(r"image\boat.bmp",cv2.IMREAD_GRAYSCALE) # 傅里叶变换 f = np.fft.fft2(img) fshift = np.fft.fftshift(f) # 高通滤波 rows,cols = img.shape crow,ccol = int(rows/2),int(cols/2) fshift[crow-30:crow+30,ccol-30:ccol+30] = 0 # 逆傅里叶变换 ishift = np.fft.ifftshift(fshift) iimg = np.fft.ifft2(ishift) iimg = np.abs(iimg) plt.subplot(1,2,1) plt.imshow(img,cmap=plt.cm.gray) plt.title("original") plt.axis("off") plt.subplot(1,2,2) plt.imshow(iimg,cmap=plt.cm.gray) plt.title("iimg") plt.axis("off") plt.show 使用numpy实现高通滤波的实验结果: 二、opencv实现傅里叶变换和逆傅里叶变换 1.opencv实现傅里叶变换 返回结果 = cv2.dft(原始图像,转换标识)1> 返回结果:是双通道的,第一个通道是结果的实数部分,第二个通道是结果的虚数部分2> 原始图像:输入图像要首先转换成np.float32(img)格式3> 转换标识:flags = cv2.DFT_COMPLEX_OUTPUT,输出一个复数阵列numpy.fft.fftshift将零频率分量移到频谱中心(将左上角的低频区域,移到中心位置)调整频谱的范围,将上面频谱图像的复数数组,转换为可以显示的灰度图像(映射到[0,255]区间)返回值 = 20*np.log(cv2.magnitude(参数1,参数2))1> 参数1:浮点型X坐标值,也就是实部2> 参数2:浮点型Y坐标值,也就是虚部 # 将绘制的图显示在窗口 %matplotlib qt5 import cv2 import numpy as np import matplotlib.pyplot as plt img = cv2.imread(r"image\lena.bmp",cv2.IMREAD_GRAYSCALE) # 傅里叶变换 dft = cv2.dft(np.float32(img),flags = cv2.DFT_COMPLEX_OUTPUT) # 移动中心位置 dftShift = np.fft.fftshift(dft) # 调整频谱的范围 result = 20*np.log(cv2.magnitude(dftShift[:,:,0],dftShift[:,:,1])) plt.subplot(1,2,1) plt.imshow(img,cmap=plt.cm.gray) plt.title("original") plt.axis("off") plt.subplot(1,2,2) plt.imshow(result,cmap=plt.cm.gray) plt.title("result") plt.axis("off") plt.show 傅里叶变换的频谱图像: 2.opencv实现逆傅里叶变换返回结果 = cv2.idft(原始数据)1> 返回结果:取决于原始数据的类型和大小2> 原始数据:实数或者复数均可numpy.fft.ifftshiftfftshift函数的逆函数,将中心位置的低频,重新移到左上角调整频谱的范围,映射到[0,255]区间返回值 = cv2.magnitude(参数1,参数2)1> 参数1:浮点型X坐标值,也就是实部2> 参数2:浮点型Y坐标值,也就是虚部 # 将绘制的图显示在窗口 %matplotlib qt5 import cv2 import numpy as np import matplotlib.pyplot as plt img = cv2.imread(r"image\lena.bmp",cv2.IMREAD_GRAYSCALE) # 傅里叶变换 dft = cv2.dft(np.float32(img),flags = cv2.DFT_COMPLEX_OUTPUT) dftShift = np.fft.fftshift(dft) # 逆傅里叶变换 ishift = np.fft.ifftshift(dftShift) iimg = cv2.idft(ishift) iimg = cv2.magnitude(iimg[:,:,0],iimg[:,:,1]) plt.subplot(1,2,1) plt.imshow(img,cmap=plt.cm.gray) plt.title("original") plt.axis("off") plt.subplot(1,2,2) plt.imshow(iimg,cmap=plt.cm.gray) plt.title("inverse") plt.axis("off") plt.show 将一副图像,进行傅里叶变换和逆傅里叶变换后,进行对比(一样的) 实例:通过opencv实现低通滤波,模糊一副图像
-
你对递归的理解是否真正掌握了C语言中的应用?
-
深入理解mxgraph系列【3】:探究底层状态树中的mxCell
-
【摩尔线程+Colossal-AI强强联手】MusaBert登上CLUE榜单TOP10:技术细节揭秘 - 技术实力:摩尔线程凭借"软硬兼备"的技术底蕴,让MusaBert得以从底层优化到顶层。其内置多功能GPU配备AI加速和并行计算模块,提供了全面的AI与科学计算支持,为AI推理和低资源条件下的大模型训练等场景带来了高效、经济且环保的算力。 - 算法层面亮点:依托Colossal-AI AI大模型开发系统,MusaBert在训练过程中展现出了卓越的并行性能与易用性,特别在预处理阶段对DataLoader进行了优化,适应低资源环境高效处理海量数据。同时,通过精细的建模优化、领域内数据增强以及Adan优化器等手段,挖掘和展示了预训练语言模型出色的语义理解潜力。基于MusaBert,摩尔线程自主研发的MusaSim通过对比学习方法微调,结合百万对标注数据,MusaSim在多个任务如语义相似度、意图识别和情绪分析中均表现出色。 - 数据资源丰富:MusaBert除了自家高质量语义相似数据外,还融合了悟道开源200GB数据、CLUE社区80GB数据,以及浪潮公司提供的1TB高质量数据,保证模型即便在较小规模下仍具备良好性能。 当前,MusaBert已成功应用于摩尔线程的智能客服与数字人项目,并广泛服务于语义相似度、情绪识别、阅读理解与声韵识别等领域。为了降低大模型开发和应用难度,MusaBert及其相关高质量模型代码已在Colossal-AI仓库开源,可快速训练优质中文BERT模型。同时,通过摩尔线程与潞晨科技的深度合作,仅需一张多功能GPU单卡便能高效训练MusaBert或更大规模的GPT2模型,显著降低预训练成本,进一步推动双方在低资源大模型训练领域的共享目标。 MusaBert荣登CLUE榜单TOP10,象征着摩尔线程与潞晨科技联合研发团队在中文预训练研究领域的领先地位。展望未来,双方将携手探索更大规模的自然语言模型研究,充分运用上游数据资源,产出更为强大的模型并开源。持续强化在摩尔线程多功能GPU上的大模型训练能力,特别是在消费级显卡等低资源环境下,致力于降低使用大模型训练的门槛与成本,推动人工智能更加普惠。而潞晨科技作为重要合作伙伴,将继续发挥关键作用。
-
超八成程序员被这道Netty面试题难住:能说说你对Pipeline工作机制的理解吗?
-
对GTD理论的初步理解和感想:读完《搞定3》的心得体会
-
面试官:说说你对 TypeScript 中泛型的理解?应用场景?
-
理解进化树的基本要点与概念简介
-
三步阅读法详解:第三次阅读 - 消化与转化篇。深入研读后,我们领略了书籍精华,但关键在于将这些精彩之处内化为个人的知识。为了真正吸收并掌握,第三次阅读需聚焦于思考:书中知识如何能应用到自己生活或工作中?又该如何从不同角度实施?通过实践应用,进一步深化对原作的理解和领悟。