为什么要使用索引?
原文地址:https://blog.csdn.net/bruce_6/article/details/84938307
用过 MySQL 的应该都知道索引是干啥的吧,应该多少都设置过索引,但是若是问你索引是怎么实现的,你能说上来吗?
这里就有了 B树(Balanced Tree)。
索引是什么?
MySQL 官方对索引的定义为:索引是帮助 MySQL 高效获取数据的数据结构。在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。 索引的出现就是为了提高查询效率,就像书的目录。其实说白了,索引要解决的就是查询问题。 查询,是数据库所提供的一个重要功能,我们都想尽可能快的获取到目标数据,因此就需要优化数据库的查询算法,选择合适的查询模型来实现索引。 另外,为表设置索引要付出代价的:一是增加了数据库的存储空间,二是在插入和修改数据时要花费较多的时间,因为索引也要随之变动。
常见查询模型
索引的实现模型有很多,这里我们先了解一下常用的查询模型。顺序数组
顺序数组是一种特殊的数组,里面的元素,按一定的顺序排列。 顺序数组在查询上有着一定的优势,因为是有序的数据,采用二分查找的话,时间复杂度是 O(log(N))。 顺序数组的优点就是查询效率非常高,但是要更新数据的话,就非常麻烦了。删除和插入元素都要涉及到大量元素位置的移动,成本很高。 因此,对于顺序数组更适合用于查询的领域,适合存储一些改动较小的静态存储引擎。哈希索引
哈希表是一种以 键-值(key-value) 存储数据的结构,我们只要输入待查找的值即 key,就可以找到其对应的值即 value。 哈希索引采用一定的哈希算法,对于每一行,存储引擎计算出了被索引字段的哈希码(Hash Code),把哈希码保存在索引中,并且保存了一个指向哈希表中的每一行的指针。 这样在检索时只需一次哈希算法即可立刻定位到相应的位置,速度非常快。 Hash 索引结构的特殊性,其检索效率非常之高,应该是 O(1) 的时间复杂度。 虽然 Hash 索引效率高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端,主要有以下这些: 1、Hash索引仅仅能满足 =,IN 和 <=> 查询,如果是范围查询检索,这时候哈希索引就毫无用武之地了。 因为原先是有序的键值,经过哈希算法后,有可能变成不连续的了,就没办法再利用索引完成范围查询检索; 2、Hash 索引无法利用索引完成排序,因为存放的时候是经过 Hash 计算过的,计算的 Hash 值和原始数据不一定相等,所以无法排序; 3、联合索引中,Hash 索引不能利用部分索引键查询。 Hash 索引在计算 Hash 值的时候是联合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值。 所以对于联合索引中的多个列,Hash 是要么全部使用,要么全部不使用。通过前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。 4、Hash索引在任何时候都不能避免表扫描。 前面已经知道,Hash 索引是将索引键通过 Hash 运算之后,将 Hash 运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中,由于不同索引键可能存在相同 Hash 值,所以即使取满足某个 Hash 键值的数据的记录条数,也无法从 Hash 索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。 5、在有大量重复键值情况下,哈希索引的效率也是极低的,因为存在所谓的哈希碰撞问题。 综上,哈希表这种结构适用于只有等值查询的场景,比如 Memcached、redis 及其他一些 NoSQL 引擎。二叉搜索树索引
二叉搜索树的每个节点都只存储一个键值,并且左子树(如果有)所有节点的值都要小于根节点的值,右子树(如果有)所有节点的值都要大于根节点的值。 当二叉搜索树的所有非叶子节点的左右子树的节点数目均保持差不多时(平衡),这时树的搜索性能逼近二分查找;并且它比连续内存空间的二分查找更有优势的是,改变树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销。 特殊情况下,根节点的左右子树的高度相差不超过 1 时,这样的二叉树被称为平衡二叉树;与之相对的是,二叉搜索树有可能退化成线性树。 下图展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。 为了加快 Col2 的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)
的复杂度内获取到相应数据。
B树
看得出来,二叉树在查询和修改上做到了一个平衡,都有着不错的效率,但是现实是很少有数据库引擎使用二叉树来实现索引,为什么呢? 数据库存储大多不适用二叉树,数据量较大时,树高会过高。 你可以想象一下一棵 100 万节点的平衡二叉树,树高 20,每个叶子结点就是一个块,每个块包含两个数据,块之间通过链式方式链接。 树高 20 的话,就要遍历 20 个块才能得到目标数据,索引存储在磁盘时,这将是非常耗时的。 因此,为了减少磁盘的读取,查询时就要尽量少的遍历数据块,因此一般使用 N 叉树。这里就有了 B树(Balanced Tree)。
究竟什么是 B 树?
我们先看一个例子: 从上图你能轻易的看到,一个内结点 x 若含有 n[x] 个关键字,那么 x 将含有 n[x]+1 个子女。如含有 2 个关键字 D H 的内结点有 3 个子女,而含有 3 个关键字 Q T X 的内结点有 4 个子女。B 树的特性
普及一些概念:节点的度:一个节点含有的子树的个数称为该节点的度; 树的度:一棵树中,最大的节点的度称为树的度; 叶节点或终端节点:度为零的节点; 非终端节点或分支节点:度不为零的节点;首先定义两个变量:d 为大于 1 的一个正整数,称为 B 树的度。h 为一个正整数,称为 B 树的高度。 B 树是满足下列条件的数据结构: 1、每个非叶子节点由 n-1 个 key 和 n 个指针组成,其中 d<=n<=2d。 2、每个叶子节点最少包含一个 key 和两个指针,最多包含 2d-1 个 key 和 2d 个指针,叶节点的指针均为 null 。 3、除根结点和叶子结点外,其它每个结点至少有 [ceil(m / 2)] 个孩子(其中 ceil(x) 是一个取上限的函数); 4、所有叶节点具有相同的深度,等于树高 h,且叶子结点不包含任何关键字信息。 5、key 和指针互相间隔,节点两端是指针。 6、一个节点中的 key 从左到右非递减排列。 7、每个指针要么为 null,要么指向另外一个节点。 8、每个非终端结点中包含有 n 个关键字信息: (n,P0,K1,P1,K2,P2,…,Kn,Pn)。 其中: a) Ki (i=1…n) 为关键字,且关键字按顺序升序排序 K(i-1)< Ki。 b) Pi 为指向子树根的接点,且指针 P(i-1) 指向子树种所有结点的关键字均小于 Ki,但都大于 K(i-1)。 c) 关键字的个数 n 必须满足: [ceil(m / 2)-1]<= n <= m-1。
目前评论:1