html简单网站成品免费,wordpress页面可以收录文章不收录,优化网络的软件,购物网站主页模版B-/B树看 MySQL索引结构
B-树
B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树.它类似普通的平衡二叉树#xff0c;不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图.
B-树有如下特点: 所有键值分布在整颗树中#xff1b; 任何一…B-/B树看 MySQL索引结构
B-树
B-树,这里的 B 表示 balance( 平衡的意思),B-树是一种多路自平衡的搜索树.它类似普通的平衡二叉树不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图.
B-树有如下特点: 所有键值分布在整颗树中 任何一个关键字出现且只出现在一个结点中 搜索有可能在非叶子结点结束 在关键字全集内做一次查找,性能逼近二分查找
B 树
B树是B-树的变体也是一种多路搜索树, 它与 B- 树的不同之处在于: 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data) 为所有叶子结点增加了一个链指针 简化 B树 如下图
为什么使用B-/B Tree
红黑树等数据结构也可以用来实现索引但是文件系统及数据库系统普遍采用B-/Tree作为索引结构。MySQL 是基于磁盘的数据库系统,索引往往以索引文件的形式存储的磁盘上,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取I/O存取的消耗要高几个数量级,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。为什么使用B-/Tree还跟磁盘存取原理有关。 局部性原理与磁盘预读 由于磁盘的存取速度与内存之间鸿沟,为了提高效率,要尽量减少磁盘I/O.磁盘往往不是严格按需读取而是每次都会预读,磁盘读取完需要的数据,会顺序向后读一定长度的数据放入内存。而这样做的理论依据是计算机科学中著名的局部性原理 当一个数据被用到时其附近的数据也通常会马上被使用 程序运行期间所需要的数据通常比较集中 由于磁盘顺序读取的效率很高(不需要寻道时间只需很少的旋转时间)因此对于具有局部性的程序来说预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。 MySQL(默认使用InnoDB引擎),将记录按照页的方式进行管理**,每页大小默认为16K(这个值可以修改)**.linux 默认页大小为4K
B-/Tree索引的性能分析
实际实现B-Tree还需要使用如下技巧 每次新建节点时直接申请一个页的空间这样就保证一个节点物理上也存储在一个页里加之计算机存储分配都是按页对齐的就实现了一个结点只需一次I/O。 假设 B-Tree 的高度为 h,B-Tree中一次检索最多需要h-1次I/O根节点常驻内存渐进复杂度为O(h)O(logdN)O(h)O(logdN)。一般实际应用中出度d是非常大的数字通常超过100因此h非常小通常不超过3。 而红黑树这种结构h明显要深的多。由于逻辑上很近的节点父子物理上可能很远无法利用局部性所以红黑树的I/O渐进复杂度也为O(h)效率明显比B-Tree差很多。
B-Tree和BTree中为什么优先选择BTree
B树更适合外部存储,由于内节点无 data 域,一个结点可以存储更多的内结点,每个节点能索引的范围更大更精确,也意味着 B树单次磁盘IO的信息量大于B-树,I/O效率更高。 Mysql是一种关系型数据库区间访问是常见的一种情况B树叶节点增加的指向相邻节点的链指针,加强了区间访问性可使用在范围区间查询等而B-树每个节点 key 和 data 在一起则无法区间查找(between, ,)。
BTree的定义
BTree是B树的变种有着比B树更高的查询性能来看下m阶BTree特征 有m个子树的节点包含有m个元素B-Tree中是m-1 根节点和分支节点中不保存数据只用于索引所有数据都保存在叶子节点中。 所有分支节点和根节点都同时存在于子节点中在子节点元素中是最大或者最小的元素。 叶子节点会包含所有的关键字以及指向数据记录的指针并且叶子节点本身是根据关键字的大小从小到大顺序链接。 红点表示是指向卫星数据的指针指针指向的是存放实际数据的磁盘页卫星数据就是数据库中一条数据记录。 叶子节点中还有一个指向下一个叶子节点的next指针所以叶子节点形成了一个有序的链表方便遍历B树。
B树的优势
1.更加高效的单元素查找 B树的查找元素3的过程 第一次磁盘IO
第二次磁盘IO
第三次磁盘IO
这个过程看下来貌似与B树的查询过程没有什么区别。但实际上有两点不一样 a、首先B树的中间节点不存储卫星数据所以同样大小的磁盘页可以容纳更多的节点元素如此一来相同数量的数据下B树就相对来说要更加矮胖些磁盘IO的次数更少。 b、由于只有叶子节点才保存卫星数据B树每次查询都要到叶子节点而B树每次查询则不一样最好的情况是根节点最坏的情况是叶子节点没有B树稳定。 2.叶子节点形成有顺链表范围查找性能更优 B树范围查找3-8的过程 a、先查找3
b、再查找4、5、6、7、8中间过程省略直接到8的查找
这里查找的范围跨度越大则磁盘IO的次数越多性能越差。 B树范围查找3-11的过程
先从上到下找到下限元素3然后通过链表指针依次遍历得到元素5/6/8/9/11如此一来就不用像B树那样一个个元素进行查找。
总结
1.单节点可以存储更多的元素使得查询磁盘IO次数更少。 2.所有查询都要查找到叶子节点查询性能稳定。 3.所有叶子节点形成有序链表便于范围查询。 PS:在数据库的聚集索引Clustered Index中叶子节点直接包含卫星数据。在非聚集索引NonClustered Index中叶子节点带有指向卫星数据的指针。
