mysql-索引

《InnoDB存储引擎》阅读笔记

B-树 ( Balanced Tree)

在计算机科学中,B树是自平衡树数据结构。其保持数据排序,并允许在对数时间内完成搜索、顺序存取、插入和删除。 B树是二叉搜索树的泛化,其节点可以具有多于两个的子节点。

与自平衡二叉搜索树不同的是,B树针对读取和写入大数据块的系统进行了优化。 B树是外部存储器的数据结构的一个很好的例子。 它通常用于数据库和文件系统。

上图展示了一种可能的索引方式:

mkJehR.png

左边是数据表,一共有两列七条记录。
最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。
为了加快 Col2 的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针。这样就可以运用二叉查找在 O(log2n) 的复杂度内获取到相应数据。

B+树 ( Balanced+ Tree)

B+的特性:

  1. 所有数据都存储在叶子结点的链表中,且链表中的数据都是有序存放的;
  2. 叶子节点间用指针相连。
  3. 不可能在非叶子结点命中;
  4. 非叶子结点相当于是叶子结点的索引,叶子结点相当于是存储数据的数据层;
  5. 更适合文件索引系统;

B+的性能:等于在数据集合做一次二分查找;

一颗二阶的 B+Tree

mkJlnO.png

与B-Tree的区别:

  • B+树只有达到叶子结点才命中。
  • B-树可以在非叶子结点命中。

B+ 树是可变的 n 元树,通常每个节点具有大量子节点。
B+ 树由根,内部节点和叶组成。根可以是叶或具有两个或更多个子节点的节点。

B+ 树可以被视为B树,其中每个(内部)节点仅包含键(不是键值对),并在其底部附加一层链式的叶子节点。

B +树的主要价值在于存储数据,以便在面向块的存储上下文(特别是文件系统)中进行高效检索。
这主要是因为,与二叉搜索树不同的是,B +树具有非常高的扇出(节点中指向 子节点的指针数,通常大约为100或更多),这减少了在树中查找元素所需的I / O操作数。

B+树索引被广泛应用于数据库、文件系统等场景。顺便说一下,xfs文件系统比ext3/ext4效率高很多的原因之一就是,它的文件及目录索引结构全部采用B+树索引,而ext3/ext4的文件目录结构则采用Linked list, hashed B-tree、Extents/Bitmap等索引数据结构,因此在高I/O压力下,其IOPS能力不如xfs。

B*树

B*树是B+树的变种,相对于B+树他们的不同之处如下:

  • 首先是关键字个数限制问题,B+树初始化的关键字初始化个数是cei(m/2),b树的初始化个数为(cei(2/3m))
  • B+树节点满时就会分裂,而B*树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针),如果兄弟节点未满则向兄弟节点转移关键字,如果兄弟节点已满,则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来;

mkNVAg.jpg

特点

  • 在B+树的基础上因其初始化的容量变大,使得节点空间使用率更高
  • 而又存有兄弟节点的指针,可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少;

创建索引可以大大提高系统的性能:

  • 可以显著提升数据的检索速度,这也是创建索引的最主要的原因。
  • 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。
  • 可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。
  • 在使用分组和排序子句进行数据检索时,同样可以显著减少查询中分组和排序的时间。
  • 通过使用索引,可以在查询的过程中,使用优化隐藏器,提高系统的性能。

增加索引也有许多不利的方面:

  • 创建索引和维护索引要耗费时间。这种时间随着数据量的增加而增加。
  • 索引需要占物理空间。除了数据表占数据空间之外,每一个索引还要占一定的物理空间。如果要建立聚簇索引,那么需要的空间就会更大。
  • 当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。

根据数据库的功能,可以在数据库设计器中创建三种索引:唯一索引、主键索引和聚集索引。

索引的实现之:Hash 索引

哈希索引采用哈希算法,把键值换算成哈希值,检索时不需要类似B+树那样从根节点到叶子节点逐级查找,只需一次哈希算法即可立刻定位到相应的位置,速度非常快。

mkJdjf.jpg

从上面的图来看,B+树索引和哈希索引的明显区别是:

  • 如果是等值查询,那么哈希索引明显有绝对优势。
    因为只需要经过一次算法即可找到相应的键值;当然了,这个前提是,键值都是唯一的。如果键值不是唯一的,就需要先找到该键所在位置,然后再根据链表往后扫描,直到找到相应的数据;
  • 如果是范围查询检索,这时候哈希索引就毫无用武之地了。
    因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了,就没办法再利用索引完成范围查询检索;哈希索引也没办法利用索引完成排序,以及like ‘xxx%’ 这样的部分模糊查询(这种部分模糊查询,其实本质上也是范围查询);
  • 哈希索引也不支持多列联合索引的最左匹配规则;
    B+树索引的关键字检索效率比较平均,不像B树那样波动幅度大,在有大量重复键值情况下,哈希索引的效率也是极低的,因为存在所谓的哈希碰撞问题。

B+树索引

数据库中的B+树索引可以分为聚集索引和非聚集索引 都是B+树实现的 高度平衡 叶子结点存放的都是数据 不同的是聚集索引叶子结点存放的是一条完整行记录 非聚集索引叶子结点存放的是主键字段。

如果某个字段的取值范围很广,几乎没有重复性,即高选择性,只会选中很少一部分行记录时x,此时适合B+树索引。

聚集索引

数据页结点存放的是完整行记录 非数据页结点存放的是键值(主键字段)以及指向数据页的偏移量

mkBqGF.jpg

辅助索引

叶子结点除了键值以外 还包含一个书签 也就是需要找的行记录的聚集索引键

mkrSyj.jpg

Donate here.