B+Tree详解-程序员宅基地

技术标签： Java B+Tree 数据结构 b树

二叉查找树：

二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。

但是当二叉查找树在极端情况下如果编程这样：

查询效率就低了

所谓查询效率：由树的深度决定，每深入一层，都需要进行寻址，而寻址的过程就是磁盘随机度，磁盘随机读的速度很慢。

平衡二叉树（AVL树）：

平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1，就达到了所谓的平衡。需要通过一系列复杂的旋转达到平衡。

B-Tree（平衡多叉查找树）：

B-Tree是为磁盘等外存储设备设计的一种平衡查找树。

上图中的每走一次箭头，都意味着一次磁盘随机IO，意味着磁臂去寻址，很慢。

每一个节点，意味着一个页空间，一个页空间默认大小为16KB，可设置。

B-Tree就是为了磁盘等外设存储设备的机理设计的一种平衡查找树，利用了磁盘块空间，把磁盘块空间充分利用，多存储几个键值、指针，通过这样的方式，可以减少树的深度，也就意味着减少磁盘的随机IO次数，加快访问速度。

B+Tree：

在B-Tree的基础上优化了：

1、节点上只存储键值，不存储数据，这样一来，在有限的节点空间（页空间）内就可以存放更多的键值、指针；

2、所有数据都放在叶子节点中，所有叶子节点之间有链指针（双向循环列表），便于范围查找，也便于排序。

InnoDB的索引使用的是B+Tree结构，那么为什么InnoDB的主键最好要搞成有序的？

InnoDB中主键索引是聚集索引，所有数据都存在主键索引所在的聚集索引的B+Tree结构的叶子节点中。如果每次插入的主键是大小随机的话，每次数据进来找到的叶子节点的位置是随机的，这样的话，有些叶子节点所在页本来就排满了，结果又来了一条数据，就势必要引起页分裂，所以导致性能下降；但是如果主键是有序的话，每次进行都找到当前叶子前面的位置，一个一个叶子按顺序排满一个页再排一个页，就不会又页分裂的问题了。所以自增主键对于InnoDB这种使用B+Tree索引的存储引擎来说，性能更好。

本文链接：https://blog.csdn.net/weixin_35794878/article/details/122609218

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

oracle瘦身,数据库瘦身-程序员宅基地

文章浏览阅读623次。今天同事通知数据库当掉了，起不来了，我看了看是内存空间满了。于是删了两个文件里的东西1、/opt/oracle/admin/orcl/bdump下的2、/opt/oracle/flash_recovery_area/ORCL物理删除以后进入数据库删除记录3、我们都知道在controlfile中记录着每一个archivelog的相关信息，当然我们在OS下把这些物理文件delete掉后，在我们的con..._oracle 瘦身

剑网三lua脚本 lua白名单插件编写（打个广告）_剑三白名单接口怎么设置-程序员宅基地

文章浏览阅读7.8k次，点赞2次，收藏18次。剑网重置版lua教程第一课：什么是lua第二课：使用lua和lua函数第三课：封装一个无参call第四课：封装一个有参call第五课：封装一个有返回的call第六课：建立易语言lua测试环境第七课：封装屏幕输出第八课：封装寻路call第九课：lua接口封装的几种形式第十课：lua的基础库和变量、数组第十一课：主线程调用第十二课：lua主线程调用第十三课：什么是游戏的lua..._剑三白名单接口怎么设置

【2012.11.8】VS2010 单元测试详解_vs单元测试是一个参数一个测试吗-程序员宅基地

文章浏览阅读157次。Visual Studio 2010 单元测试之一---普通单元测试本文以Visual Studio 2010为例，来介绍如何在Visual Studio里面进行单元测试.首先来介绍普通单元测试，这是进行顺序测试、压力测试的基础。如果在Visual Studio 2010(2008)里面没有发现下图中的Test菜单，请用Visual Studio安装光盘进行安装，因为Visual Stud_vs单元测试是一个参数一个测试吗

Android -- Wifi的forget()操作_mwifimanager.forget-程序员宅基地

文章浏览阅读6.3k次。Android -- Wifi的forget()操作我们在处理某个Wifi连接时，有时会需要忘掉当前连接的密码信息。执行这项操作，我们需要调用WifiManager::forget()函数： /** * Delete the network in the supplicant config. * * This function is used ins_mwifimanager.forget

WebGL 雨水特效_webgl water-程序员宅基地

文章浏览阅读2.7k次。今天我们将要和大家分享一些 WebGL 实验，在这个实验中我们将创建一个非常逼真的雨滴效果，并把它放到不同的场景中去。在这篇文章中，我们将给出制作这种效果所用到的一些一般性技术和技巧的概览。请注意：文中制作的效果还处于试验阶段，可能无法在所有浏览器中都看到预期的效果。最好使用 Chrome。入门如果我们想制作一个基于现实世界的效果，那么首先我们需要剖析一下它看起来究竟是什么_webgl water

秒杀面试中的股票问题，看这一篇就够了_面试题推荐股票-程序员宅基地

文章浏览阅读645次。秒杀面试中的股票问题，看这一篇就够了大家好，今天这片文章总结一下leetcode中所有的股票问题的通用解法。股票问题是动态规划的一类题目，在面试中非常常见，而且变化很多，着实让人头疼。今天这篇文章归纳出股票问题的模版，之后遇到不同的股票问题，就可以用这套模版秒杀了。为什么单独提出来股票问题我们看一下leetcode的123题：Best Time to Buy and Sell Stock I..._面试题推荐股票

随便推点

关于画图软件Dia打开程序始终为英文界面的问题-程序员宅基地

文章浏览阅读203次。按官方的意思，打开程序应该能够识别当前操作系统的语言，进而选择合适的语言界面。其它几个电脑试了一下，的确是没有问题，但是在我的电脑上就是不行。最后在用户环境变量中加了LANG=zh_CN之后，再重启程序就OK了，中文界面出现了。最后发现，原来我在系统变量中加过一个同名的变量，难怪……转载于:https://www.cnblogs.com/mittyok/archive/2012..._画图工具变成英文怎么回事

OpenCV从入门到精通实战(二)——文档OCR识别（tesseract）-程序员宅基地

文章浏览阅读1.4k次，点赞20次，收藏15次。对四个坐标点进行排序，确定文档的四个角（左上，右上，右下，左下）。使用欧氏距离来计算和排序点。# 一共4个坐标点# 按顺序找到对应坐标0123分别是左上，右上，右下，左下# 计算左上，右下# 计算右上和左下此函数用于排序提供的四个点，确保点的顺序为左上、右上、右下和左下，这对后续的透视变换非常重要。使用cv2.getPerspectiveTransform和cv2.warpPerspective来计算变换矩阵并应用# 获取输入坐标点# 计算输入的w和h值# 变换后对应坐标位置。

详解avcodec_receive_packet 11_avcodec_receive_packet eagain-程序员宅基地

文章浏览阅读1.3k次，点赞38次，收藏21次。cCopy codeavcodec_receive_packet函数用于从编码器上下文avctx中接收输出的数据包，保存在AVPacket结构体avpkt中。该函数通常与avcodec_send_frame函数配合使用，用于编码器的数据输入和输出。在本文中，我们详细介绍了avcodec_receive_packet函数的用法和参数，以及其在音视频处理中的作用。通过合理使用avcodec_receive_packet函数，我们可以从编码器中接收到输出的数据包，进一步处理和使用。_avcodec_receive_packet eagain