本篇文章主要学习了MySQL的索引的数据结构的认识,做一个大概的了解即可。 一、索引在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储数据结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录,可以根据目录中的页码快速查找到所需的内容。 在MySQL中,存储引擎用类似的方法使用索引,先在索引中找到对应值,然后根据匹配的索引记录找到对应的行。 首先说明下MySQL的索引主要是基于Hash表或者B 树。 二、索引数据结构了解索引就需要从索引常见的数据结构开始了解学习,这里有集中常见的的索引数据结构。 二叉树(Binary Trees) 二叉树是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常被称之为“左子树”和“右子树” 左子树<父节点<=右子树 二叉树的第i层至多有有2^(i-1)个节点, 深度为K的二叉树至多总共有个2^k-1节点(定义根节点所在深度 k0=0),而总计拥有节点数符合的,称为“满二叉树”; 二叉树通常作为数据结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆,并应用于高效率的搜索和排序。 同时学习数据结构,这里还推荐Data Structure Visualizations进行学习,可以非常直观的看到数据结构允许的过程,一步一步的怎么走的都可以很清晰看得到。 找到其中的Binary Search Trees二叉树 可以直观的看到二叉树的数据插入过程,如下: 可以看到二叉树不适合用作当作索引的,数据量庞大的话,二叉树的层数会很大,查找效率固然也很慢了。 红黑树(Red-Black Trees) 是一种自平衡二叉查找树,典型用途是实现关联数组。 红黑树的结构复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中高效:它可以在O(log n)时间内完成查找,插入和删除,这里的n是树中元素的数目。 红黑树遵行以下原则:
下面是一个具体的红黑树的图例: 这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。 要知道为什么这些性质确保了这个结果,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。 同样在Data Structure Visualizations中选择Red-Black Trees红黑树进行插入操作可以直观的看到红黑树的插入过程 同样红黑树也不适用于MySQL的索引,数据量庞大之后,数层也会变大。 其他结构的问题 由于无法装入内存,则必然依赖磁盘(或SSD)存储。而内存的读写速度是磁盘的成千上万倍(与具体实现有关),因此,核心问题是“如何减少磁盘读写次数”。 首先不考虑页表机制,假设每次读、写都直接穿透到磁盘,那么:
BST、AVL、RBT很好的将读写次数从O(n)优化到O(log2(n));其中,AVL和RBT都比BST多了自平衡的功能,将读写次数降到最大O(log2(n))。 假设使用自增主键,则主键本身是有序的,树结构的读写次数能够优化到树高,树高越低读写次数越少;自平衡保证了树结构的稳定。如果想进一步优化,可以引入B树和B 树。 B树(B-Trees) 又称:多路平衡查找树。大多数存储引擎都支持B树索引。b树通常意味着所有的值都是按顺序存储的,并且每一个叶子节点到根的距离相同。B树索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取数据。下图就是一颗简单的B树。 在B树中,内部(非叶子)节点可以拥有可变数量的子节点(数量范围预先定义好)。当数据被插入或从一个节点中移除,它的子节点数量发生变化。为了维持在预先设定的数量范围内,内部节点可能会被合并或者分离。 如下图所示:
只演示了插入的过程,其中可以通过delete、find执行删除和查找操作。直观的感受到B树的执行过程。 每个节点存储了多个Key和子树,子树与Key按顺序排列。
假设key、子树节点指针均占用4B,则B树节点最大m * (4 4) = 8m B;页面大小4KB。则m = 4 * 1024 / 8m = 512,一个512叉的B树,1000w的数据,深度最大 log(512/2)(10^7) = 3.02 ~= 4。对比二叉树如AVL的深度为log(2)(10^7) = 23.25 ~= 24,相差了5倍以上。震惊!B树索引深度竟然如此! 那为什么B数这么厉害了,还有B 树的出现呢,必然是解决B树存在的问题 1、为定位行数 2、无法处理范围查询 问题1:为定位行数 数据表的记录有多个字段,仅仅定位到主键是不够的,还需要定位到数据行。有3个方案解决:
方案1直接pass,存储数据行将减少页面中的子树个数,m减小树高增大。 方案2的节点中增加了一个字段,假设是4B的指针,则新的m = 4 * 1024 / 12m = 341.33 ~= 341,深度最大 log(341/2)(10^7) = 3.14 ~= 4。 方案3的节点m与深度不变,但时间复杂度变为稳定的O(logm(n))。 方案3可以考虑。 问题2:无法处理范围查询 实际业务中,范围查询的频率非常高,B树只能定位到一个索引位置(可能对应多行),很难处理范围查询。改动较小的是2个方案:
乍一看感觉方案1比方案2好——时间复杂度和常数项都一样,方案1还不需要改动。但是别忘了局部性原理,不管节点中存储的是数据行还是数据行位置,方案2的好处在于,依然可以利用页表和缓存预读下一节点的信息。而方案1则面临节点逻辑相邻、物理分离的缺点。 B 树(B Trees) 主要变动如上所述:
回顾上一个B树,一个m阶的B树具有如下几个特征: 1.根结点至少有两个子女。 2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m 3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m 4.所有的叶子结点都位于同一层。 5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。 一个m阶的B 树具有如下几个特征: 1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。 2.所有的叶子结点包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。 B 树特性总结 B 树是B树的升级版,其有如下特性
同样在Data Structure Visualizations中选择B TreesB 树进行插入操作可以直观的看到插入过程 在动图中可以看出,B 树的每一个叶子节点都有一个指针指向下一个节点,把所有的叶子节点串在一起。索引数据都存储在叶子节点中。 B 树相比于B树,有什么优势呢: 1.单一节点存储更多的元素,使得查询的IO次数更少。 2.所有查询都要查找到叶子节点,查询性能稳定。 3.所有叶子节点形成有序链表,便于范围查询。 总结,B 树相比B树的优势有三:1.IO次数更少;2.查询性能稳定;3.范围查询简便。 Hash索引 hash索引基于hash表实现,Hash 索引是将索引键通过 Hash 运算之后,将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中。只有精准匹配索引所有列的查询才有效。索引的检索可以一次定位,不像B-Tree索引需要从根节点出发到目标节点。虽然Hash索引很快,远高于B-tree索引,但是也有其弊端。
三、MySQL数据库引擎通过navicat工具查看表设计选项中,从引擎中可以看到MySQL又这么多引擎。具体细分到每个表,不同的表引擎可以不一样。 MyISAM 新建一张表t_test_myisam,引擎使用MyISAM,查看原文件可以看到有3个文件 可以看到索引和数据是分开的,其中索引文件仅仅保存数据记录的地址,故属于非聚簇索引。 主键索引(Primary Index) MyISAM引擎使用B Tree作为索引结构,叶节点的data存放的是数据记录的地址。如下图是MyISAM主键索引的原理图。 其中Col1为主键,可以看出看出MyISAM的索引文件仅保存数据记录的地址。 辅助索引(Secondary Index) 在Col2上建立一个辅助索引,如下图辅助索引原理图。 可以看到与主键索引没有任何区别,只不过主键索引的key是唯一的,而辅助索引的key可以重复。 MyISAM中索引检索的算法为首先按照B Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。 InnoDB 新建一张表t_test_innodb,引擎使用InnoDB,查看原文件可以看到有2个文件 主键索引(Primary Index) InnoDB的索引和数据在一个文件当中。 按照B Tree组织的一个索引结构。 叶节点保存了完整的数据记录和索引。这种索引就叫做聚簇索引。 索引的Key是数据的主键,因此InnoDB表数据文件本身就是主索引。 如下图: 可以看到叶节点包含了完整的数据记录。 因为InnoDB的数据文件本身要按照主键聚集,所以InnoDB要求必须有主键。如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段rowid作为主键,这个字段长度为6个字节,类型为长整形。 辅助索引(Secondary Index) 辅助索引,将途中的第二行name,作为索引如图 聚簇索引这种实现方式使得按照主键的搜索十分高效,但是首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。 由于InnoDB索引的实现特性,推荐使用整形的自增主键。 有三点好处:
InnoDB索引和MyISAM索引的区别 一是主索引的区别:InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。 二是辅助索引的区别:InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。 四、覆盖索引InnoDB存储引擎支持覆盖索引,即从辅助索引中就可以得到查询的记录,不需要查询聚簇索引中的记录了。可以减少大量的IO操作。 如果要查询辅助索引中不含有的字段,得先遍历辅助索引,再遍历聚集索引,而如果要查询的字段值在辅助索引上就有,就不用再查聚集索引了,这显然会减少IO操作。 五、联合索引两个或以上的列上的索引。如下图联合索引的原理图: 上图中的联合索引有三个,从上到下,严格按照排序。 六、优化建议最左前缀匹配 索引可以简单如一个列(a),也可以复杂如多个列(a, b, c, d),即联合索引。如果是联合索引,那么key也由多个列组成,同时,索引只能用于查找key是否存在(相等),遇到范围查询(>、<、between、like左匹配)等就不能进一步匹配了,后续退化为线性查找。因此,列的排列顺序决定了可命中索引的列数。 如有索引(a, b, c, d),查询条件a = 1 and b = 2 and c > 3 and d = 4,则会在每个节点依次命中a、b、c,无法命中d。也就是最左前缀匹配原则。 =、in自动优化顺序 不需要考虑=、in等的顺序,mysql会自动优化这些条件的顺序,以匹配尽可能多的索引列。 如有索引(a, b, c, d),查询条件c > 3 and b = 2 and a = 1 and d < 4与a = 1 and c > 3 and b = 2 and d < 4等顺序都是可以的,MySQL会自动优化为a = 1 and b = 2 and c > 3 and d < 4,依次命中a、b、c。 索引列不能参与计算 有索引列参与计算的查询条件对索引不友好(甚至无法使用索引),如from_unixtime(create_time) = '2014-05-29'。 原因很简单,如何在节点中查找到对应key?如果线性扫描,则每次都需要重新计算,成本太高;如果二分查找,则需要针对from_unixtime方法确定大小关系。 因此,索引列不能参与计算。上述from_unixtime(create_time) = '2014-05-29'语句应该写成create_time = unix_timestamp('2014-05-29')。 能扩展就不要新建索引 如果已有索引(a),想建立索引(a, b),尽量选择修改索引(a)为索引(a, b)。 新建索引的成本很容易理解。而基于索引(a)修改为索引(a, b)的话,MySQL可以直接在索引a的B 树上,经过分裂、合并等修改为索引(a, b)。 不需要建立前缀有包含关系的索引 如果已有索引(a, b),则不需要再建立索引(a),但是如果有必要,则仍然需考虑建立索引(b)。 |
|
来自: Fengsq501u81r4 > 《计算机》