良精网站管理系统,做jsp网站用哪些软件下载,wordpress 4.8.2中文,从事高端网站建设一、背景一般说MySQL的索引#xff0c;都清楚其索引主要以B树为主#xff0c;此外还有Hash、RTree、FullText。本文简要说明一下MySQL的BTree索引#xff0c;以及和其相关的二叉树、平衡二叉树、B-Tree#xff0c;相关的知识网上很多#xff0c;为了方便自己更快、清楚的了…一、背景一般说MySQL的索引都清楚其索引主要以B树为主此外还有Hash、RTree、FullText。本文简要说明一下MySQL的BTree索引以及和其相关的二叉树、平衡二叉树、B-Tree相关的知识网上很多为了方便自己更快、清楚的了解文本聚合一些内容以及个人的一些理解。二、二叉查找树BST(1)概念:二叉查找树是基于二分查找法来提高数据查找速度的二叉树的数据结构关于二分查找法的时间复杂度可以看 时间复杂度 O(log n) 意味着什么。(2)特点 二叉查找树是采用二分查找法把数据按规则组装成一个树形结构的数据减少无关数据的检索提升了数据检索的速度二叉树的数据结构有以下规则1非叶子节点只能允许最多两个子节点存在。2每一个非叶子节点数据分布规则为左边的子节点小当前节点的值右边的子节点大于当前节点的值即二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值右子节点的键值都大于当前节点的键值。 顶端的节点称为根节点没有子节点的节点我们称之为叶节点。以下图中的圆为二叉查找树的节点节点中存储了键(key)和数据(data)。查找结点值的方法就是二分查找法查找次数就是树的高度。二叉查找树可以任意地构造 如果向一方倾斜的二叉树是不平衡的查询效率就低了二叉查找树变成了一个链表。如下图 在上面的2张图中查找键值为17的数据第一张图里需要3次IO第2张图里需要7次IO。原因是二叉查找树变得不平衡了也就是高度太高了从而导致查找效率的不稳定。为了解决这个问题需要保证二叉查找树一直保持平衡就需要用到平衡二叉树了。本群免费分享学习资料(C/CLinuxgolang,NginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerffmpegTCP/IP协程DPDK嵌入式)等。更多的学习资料请加qqun:1106675687。三、平衡二叉树AVL在满足二叉查找树特性的基础上如不是空树任何一个结点的左子树与右子树都是平衡二叉树并且高度之差的绝对值不超过 1。 类似于 关于平衡二叉树的可以看 什么是平衡二叉树AVL该文章说明平衡二叉树相比于二叉查找树来说查找效率更稳定总体的查找速度也更快。需要注意的是平衡二叉树是每个节点只存储一个键值和数据的。四、B树(B-Tree)(1)概念B树和平衡二叉树不同B树属于多叉树又名平衡多路查找树查找路径不只两个数据库索引里大量使用者B-Tree和BTree的数据结构。(2)特点1排序方式所有节点关键字是按递增次序排列并遵循左小右大原则2子节点数非叶节点的子节点数1且M且M2空树除外注M阶代表一个树节点最多有多少个查找路径MM路当M2则是2叉树,M3则是3叉3关键字数枝节点的关键字数量大于等于ceil(M/2)-1个且小于等于M-1个注ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);4所有叶子节点均在同一层、叶子节点除了包含了关键字还包含了数据;最后我们用一个图和一个实际的例子来理解B树这里为了理解方便我就直接用实际字母的大小来排列CBA图中可以看到BTree的单个节点可以存储多个键值和数据的平衡树。和平衡二叉树相比 比如要存储海量的数据因为平衡二叉树的每个节点只存储一个键值和数据的二叉树的节点将会非常多高度也会及其高当查找数据时也会进行很多次磁盘IO查找的效率将会极低大致的二叉树结构如下为了解决平衡二叉树的这个弊端需要一种单个节点可以存储多个键值和数据的平衡树BTree从上图可以看出B树相对于平衡二叉树每个节点存储了更多的键值(key)和数据(data)并且每个节点拥有更多的子节点子节点的个数一般称为阶上述图中的B树为3阶B树高度也会很低。 基于这个特性B树查找数据读取磁盘的次数将会很少数据的查找效率也会比平衡二叉树高很多。假如我们要查找id28的用户信息那么我们在上图B树中查找的流程如下先找到根节点也就是页1判断28在键值17和35之间我们那么我们根据页1中的指针p2找到页3。将28和页3中的键值相比较28在26和30之间我们根据页3中的指针p2找到页8。将28和页8中的键值相比较发现有匹配的键值28键值28对应的用户信息为(28,bv)。区别B树相对于平衡二叉树的不同是每个节点包含的关键字增多了特别是在B树应用到数据库中的时候数据库充分利用了磁盘块的原理磁盘数据存储是采用块的形式存储的每个块的大小为4K每次IO进行数据读取时同一个磁盘块的数据可以一次性读取出来把节点大小限制和充分使用在磁盘快大小范围把树的节点关键字增多后树的层级比原来的二叉树少了减少数据查找的次数和复杂度。 相同数量的key在B-Tree中生成的节点要远远少于二叉树中的节点相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后性能的差异就显现出来了。五、B树BTree(1)概念B树是B树的一个进化相对于B树来说B树更充分的利用了节点的空间让查询速度更加稳定其速度完全接近于二分法查找。结构如下为什么说B树查找的效率要比B树更高、更稳定我们先看看两者的区别1.B树的非叶子节点不保存数据只进行数据索引关键字记录的指针这样使得B树每个非叶子节点所能保存的关键字大大增加2.B树叶子节点保存了父节点的所有关键字记录的指针所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样3.B树叶子节点的关键字从小到大有序排列左边结尾数据都会保存右边节点开始数据的指针4.B树非叶子节点的子节点数关键字数;(2)特点:1、B树的层级更少相较于B树B每个非叶子节点存储的关键字数更多树的层级更少所以查询数据更快2、B树查询速度更稳定B所有关键字数据地址都存在叶子节点上所以每次查找的次数都相同所以查询速度要比B树更稳定;3、B树天然具备排序功能B树所有的叶子节点数据构成了一个有序链表在查询大小区间的数据时候更方便数据紧密性很高缓存的命中率也会比B树高。4、B树全节点遍历更快B树遍历整棵树只需要遍历所有的叶子节点即可而不需要像B树一样需要对每一层进行遍历这有利于数据库做全表扫描。B树相对于B树的优点是如果经常访问的数据离根节点很近而B树的非叶子节点本身存有关键字其数据的地址所以这种数据检索的时候会要比B树快。根据上图我们来看下B树和B树有什么不同BTree 非叶子节点上是不存储数据的仅存储键值数据存储在同一层的叶节点而B-Tree节点中不仅存储键值也会存储数据。之所以这么做是因为在数据库中页的大小是固定的innodb中页的默认大小是16KB。如果不存储数据那么就会存储更多的键值相应的树的阶数(节点的子节点树)就会更大树就会更矮更胖如此一来我们查找数据进行磁盘的IO次数有会再次减少数据查询的效率也会更快。另外BTree的阶数是等于键值的数量的如果BTree一个节点可以存储1000个键值那么3层B树可以存储1000×1000×100010亿个数据。一般根节点是常驻内存的所以一般我们查找10亿数据只需要2次磁盘IO。因为BTree索引的所有数据均存储在叶子节点而且数据是按照顺序排列的。那么B树使得范围查找排序查找分组查找以及去重查找变得异常简单。而B-Tree 因为数据分散在各个节点要实现这一点是很不容易的。BTree 中各个页之间是通过双向链表连接的叶子节点中的数据是通过单向链表连接的。其实上面的B-Tree也可以对各个节点加上链表。其实这些不是它们之前的区别是因为在mysql的innodb存储引擎中索引就是这样存储的。也就是说上图中的BTree索引就是innodb中BTree索引真正的实现方式准确的说应该是聚集索引。通过上图可以看到在innodb中数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。注意MyISAM中的B树索引实现与innodb中的略有不同。在MyISAM中B树索引的叶子节点并不存储数据而是存储数据的文件地址。六、总结BTree 结构是从二叉查找树平衡二叉树和B-Tree这三种数据结构演化来的他们之前的区别上面已经介绍过现在大致的总结下如下1二叉查找树是基于二分查找法来提高数据查找速度的二叉树的数据结构减少无关数据的检索提升了数据检索的速度。非叶子节点只能允许最多两个子节点存在每一个非叶子节点数据分布规则为左边的子节点小当前节点的值右边的子节点大于当前节点的值每个节点只存储一个键值和数据的。2平衡二叉树满足二叉查找树特性的基础上如不是空树任何一个结点的左子树与右子树都是平衡二叉树并且高度之差的绝对值不超过 1。3B-TreeB和平衡二叉树不同B-Tree属于多叉树又名平衡多路查找树 B-Tree相对于平衡二叉树每个节点存储了更多的键值(key)和数据(data)并且每个节点拥有更多的子节点。4BTree和B-Tree不同BTree在非叶子节点上不保存数据只存储指针能存储更多的键值相应的树的阶数(节点的子节点树)就会更大树就会更矮更胖如此一来我们查找数据进行磁盘的IO次数有会再次减少数据查询的效率也会更快。并且B树索引的所有数据均存储在叶子节点而且数据是按照顺序排列的。那么B树使得范围查找排序查找分组查找以及去重查找变得异常简单。首先恭喜您能够认真的阅读到这里如果对部分理解不太明白建议先将文章收藏起来然后对不清楚的知识点进行查阅然后在进行阅读相应你会有更深的认知。如果您喜欢这篇文章就点个赞或者【关注我】吧
