wordpress图片轮播插件,重庆seo技术教程,福州短视频seo费用,wordpress 提速 插件文章目录 不用平衡二叉树或红黑树作为索引B树适合作为索引比B树更适合作为索引的结构——B树总结 MySQL 使用 B树索引数据结构#xff08;因为默认使用 innodb 存储引擎#xff09; B树#xff1a;有序数组 平衡多叉树#xff1b;B树#xff1a;有序数组链表 平衡多叉树… 文章目录 不用平衡二叉树或红黑树作为索引B树适合作为索引比B树更适合作为索引的结构——B树总结 MySQL 使用 B树索引数据结构因为默认使用 innodb 存储引擎 B树有序数组 平衡多叉树B树有序数组链表 平衡多叉树
不用平衡二叉树或红黑树作为索引
普通二叉树
二叉树的查找的时间复杂度是 O ( l o g 2 N ) O(log_2N) O(log2N)其查找效率与深度有关而普通的二叉树可能由于内部节点排列问题退化成链表。例如按顺序插入一组递增的数值可能导致树变成一条链表在这种情况下树的深度变为 N查找的时间复杂度退化为 O ( N ) O(N) O(N)这与链表的查找效率相同。这样查找效率就会很低。1\2\3\4平衡二叉树
平衡二叉树是更好的选择通过自平衡机制保持平衡即通过旋转调整结构保持最小的深度所有节点的左右子树高度差不能超过 1确保了查找、插入和删除操作的时间复杂度保持在 O ( l o g 2 N ) O(log_2N) O(log2N)。
为什么平衡二叉树不适合作为索引呢 索引通常存储在磁盘上的索引文件中。在数据表很大的情况下索引也会很大因此无法一次性将全部索引加载到内存当中。数据库系统通常以页如 4KB、8KB 或 16KB为单位从磁盘中读取一个磁盘页的数据量到内存中为了找到指定索引的磁盘页可能会导致多次磁盘 I/O 操作才能完成。而这个磁盘的读取的速度较内存中的读取速度而言是差了好几个级别磁盘的随机访问时间可能是内存访问时间的数百倍至数千倍这意味着每次从磁盘读取数据时都会消耗较多的时间。 每个节点只有两个子节点这导致树的高度可能较大。当树的深度增加时查找时需要的磁盘 I/O 操作也会相应增加。例如在最坏情况下查找可能需要访问树的每一层而每一层都需要从磁盘读取数据。 平衡二叉树在逻辑结构上相近的节点在树的结构中是相邻的其物理实现是使用数组来存储节点。虽然在逻辑上相邻的节点可能在物理数组中相距较远因此每次读取的磁盘页的数据中有许多是用不上的。因此查找过程中要进行许多次的磁盘读取操作。 平衡二叉树各节点之间在逻辑上存在一定的关系但在物理实现却是随机的比如父子关系或兄弟关系的两个节点子逻辑上相邻之类的但在物理实现上却是分散的。对于使用磁盘预读局部性原理每次从磁盘读取一页读取的是物理结构上连续的一段数据这样就会读取许多无用的信息接下来很大机会不会用到 其次就是二叉树每个节点只能存储一个关键字及其相关信息不能充分利用磁盘预读功能 而适合作为索引的结构应该是尽可能少的执行磁盘IO操作因为执行磁盘IO操作非常的耗时。因此平衡二叉树并不适合作为索引结构。
总结
使用红黑树平衡二叉树结构的话每次磁盘预读中的很多数据是用不上的数据。因此它没能利用好磁盘预读的提供的数据。然后又由于深度大较B树而言所以进行的磁盘IO操作更多。
B树适合作为索引
平衡二叉树没能充分利用磁盘预读功能而B树是为了充分利用磁盘预读功能来而创建的一种数据结构也就是说B树就是为了作为索引才被发明出来的的。
B 树的设计旨在最大限度地减少磁盘访问次数特别是在处理大量数据时。由于磁盘访问速度远低于内存访问速度减少 I/O 操作对于提高整体性能至关重要B 树结构允许每个节点包含多个关键字和子节点这意味着在一次磁盘读取中可以获取更多的数据。这样B树能够高效地利用磁盘的读取特性特别是在顺序访问时
B树的结构特点
多叉结构与平衡二叉树不同B 树的每个节点可以有多个子节点这使得树的高度显著降低从而减少了查找和更新时所需的 I/O 操作节点内存储多个关键字B 树的每个节点可以存储多个关键字这样在每次读取磁盘页时可以同时获取多个数据项充分利用了磁盘的预读能力
局部性原理与磁盘预读 由于存储介质的特性磁盘的存取速度远低于内存传统机械硬盘的访问时间受机械运动的影响磁盘的存取速度往往是主存的几百分分之一这使得磁盘 I/O 成为性能瓶颈尤其是在需要频繁读取数据时。因此为了提高效率要尽量减少磁盘 I/O。为了达到这个目的磁盘读取往往不是严格按需读取而是每次都会预读读取一段连续的数据称为一页即使只需要一个字节磁盘也会从这个位置开始顺序向后读取一定长度的数据放入内存。这样做的目的是利用磁盘的顺序读取特性提高读取效率。这样做的理论依据是计算机科学中著名的局部性原理 局部性原理局部性原理是指在程序运行过程中访问的数据往往集中在某些特定区域。当一个数据项被访问时其附近的数据项很可能也会被访问。这种现象在许多程序中普遍存在。由于磁盘顺序读取的效率很高不需要寻道时间只需很少的旋转时间因此对于具有局部性的程序来说预读可以提高I/O效率 在操作系统中磁盘 I/O 的读取和写入通常以页page为单位进行。页是固定大小的数据块一页的数据量有多大跟操作系统有关常见的大小有 4KB、8KB 或 16KB。也就是我们读取一页内的数据时候实际上才发生了一次IO这个理论对于索引的数据结构设计非常有帮助 磁盘预读是具体实现其理论依据是局部性原理。
B树适合作为索引
B 树的每个节点可以存储多个关键字它将节点大小设置为磁盘页的大小充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点。也正因每个节点存储着非常多个关键字树的深度就会非常的小。进而要执行的磁盘读取操作次数就会非常少更多的是在内存中对读取进来的数据进行查找。
每个节点可以存储多个关键字可以充分利用了磁盘预读的功能B 树的深度会非常的小减小磁盘 I/O 操作。
B树的查询主要发生在内存中而平衡二叉树的查询则是发生在磁盘读取中。因此虽然B树查询查询的次数不比平衡二叉树的次数少但是相比起磁盘IO速度内存中比较的耗时就可以忽略不计了。因此B树更适合作为索引。
比B树更适合作为索引的结构——B树 B树中的B不是代表二叉(binary)而是代表平衡(balance)因为B树是从最早的平衡二叉树演化而来但是 B树不是一个二叉树。 MySQL 中也是使用B树作为索引。它是B树的变种因此是基于B树来改进的。
B树的关键字全部存放在叶子节点中非叶子节点用来做索引而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问遍历的性能。 B树必须用中序遍历的方法按序扫库而B树直接从叶子结点挨个扫一遍就完了B树支持 range-query 非常方便而B树不支持。这是数据库选用B树的最主要原因。 比如说 我们要查找关键字范围在3到7的关键字在找到第一个符合条件的数字3后访问完第一个关键字所在的块后得遍历这个B树获取下一个块直到遇到一个不符合条件的关键字。遍历的过程是比较复杂的。即B树遍历完一块后需要查询B树得到下一块然后再遍历相比之下B树的基于范围的查询简洁很多。由于叶子节点有指向下一个叶子节点的指针因此从块1到块2的访问通过块1指向块2的指针即可从块2到块3也是通过一个指针即可。B树遍历完一块后可以通过指针指向下一块继续遍历B树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的而B树不支持这样的操作或者说效率太低。
b树的查找过程 如图所示如果要查找数据项29那么首先会把磁盘块1由磁盘加载到内存此时发生一次IO在内存中用二分查找确定29在17和35之间锁定磁盘块1的P2指针内存时间因为非常短相比磁盘的IO可以忽略不计通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存发生第二次IO29在26和30之间锁定磁盘块3的P2指针通过指针加载磁盘块8到内存发生第三次IO同时内存中做二分查找找到29结束查询总计三次IO。真实的情况是3层的b树可以表示上百万的数据如果上百万的数据查找只需要三次IO性能提高将是巨大的如果没有索引每个数据项都要发生一次IO那么总共需要百万次的IO显然成本非常非常高。 一颗b树浅蓝色的块我们称之为一个磁盘块可以看到每个磁盘块包含几个数据项深蓝色所示和指针黄色所示如磁盘块1包含数据项17和35包含指针P1、P2、P3P1表示小于17的磁盘块P2表示在17和35之间的磁盘块P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点不存储真实的数据只存储指引搜索方向的数据项如17、35并不真实存在于数据表中。
总结用B树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题B树应运而生。
总结
B树 B树就是一个节点可以拥有多于2个子节点的多叉查找树。 叶子节点和非叶子节点都储存关键字和真实数据项每个节点不仅用于索引还包含实际的数据。因为非叶子节点要保存数据项所以一个节点块能保存的索引少相对于B树访问磁盘IO时就多 B树是有序数组平衡多叉树
B树 B树是基于B树来改进的。 非叶子节点只存储关键字用于索引搜索路径而不存储实际的数据项所有真实数据只存储在叶子节点中。因为非叶子节点不保存数据项所以一个节点块能保存的索引多相对于B树访问磁盘IO时就少尽管在内存遍历的次数变多但内存访问比磁盘快很多相对于访问磁盘访问内存的时间几乎可以不计。 B树有序数组链表平衡多叉树 树的所有叶子节点构成一个有序链表可以按照主键排序的次序遍历全部记录。BTree 所有真实数据都在叶子节点上并且增加了顺序访问指针每个叶子节点都有指向相邻叶子节点的指针便于区间查找和遍历。
B树与B树对比
B树结构在所有的节点里存储索引信息和数据项B树结构没有在所有的节点里存储记录数据项而是只在最下层的叶子节点存储上层的所有非叶子节点只存放索引信息。B树是有序数组平衡多叉树B树是有序数组链表平衡多叉树。B树使用双向链表串连所有叶子节点区间查询效率更高因为所有数据都在B树的叶子节点但是B树则需要通过中序遍历才能完成查询范围的查找。B树每次都必须查询到叶子节点才能找到数据而B树查询的数据可能不在叶子节点也可能在这样就会造成查询的效率的不稳定。B树查询效率更高因为B树矮更胖高度小查询产生的I/O最少。因为非叶子节点不保存数据项所以一个节点块能保存的关键字索引更多所以一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
B 树的优点在于
IO次数更少相对于其他数据结构由于B树在内部节点上不包含数据信息因此在内存页中能够存放更多的key。 数据存放的更加紧密具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。 数据库系统的设计者巧妙利用了磁盘预读原理将一个节点的大小设为等于一个页这样每个节点需要一次I/O就可以完全载入。 遍历更加方便相对于B树结构B树的叶子结点都是相链的因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻所以缓存命中性没有B树好。 这样做是为了提高区间效率例如查询key为从18到49的所有数据记录当找到18后只要顺着节点和指针顺序遍历就可以以此向访问到所有数据节点极大提高了区间查询效率。
B树优点
但是B树也有优点其优点在于由于B树的每一个节点都包含key和value因此经常访问的元素可能离根节点更近因此访问也更迅速。下面是B 树和B树的区别图
为什么MySQL选择B树做索引
1、 B树的磁盘读写代价更低B树的内部节点并没有指向关键字具体信息的指针因此其内部节点相对B树更小如果把所有同一内部节点的关键字存放在同一盘块中那么盘块所能容纳的关键字数量也越多一次性读入内存的需要查找的关键字也就越多相对IO读写次数就降低了。
2、B树的查询效率更加稳定由于非终结点并不是最终指向文件内容的结点而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同导致每一个数据的查询效率相当。
3、B树更便于遍历由于B树的数据都存储在叶子结点中分支结点均为索引方便扫库只需要扫一遍叶子结点即可但是B树因为其分支结点同样存储着数据我们要找到具体的数据需要进行一次中序遍历按序来扫所以B树更加适合在区间查询的情况所以通常B树用于数据库索引。
4、B树更适合基于范围的查询B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题正是为了解决这个问题B树应用而生。B树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的而B树不支持这样的操作或者说效率太低。
参考1
参考2
