MySql索引原理总结

2019-03-07 本文已影响0人 whupenger

索引是一个排序的列表，在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址，在数据十分庞大的时候，索引可以大大加快查询的速度，这是因为使用索引后可以不用扫描全表来定位某行的数据，而是先通过索引表找到该行数据对应的物理地址然后访问相应的数据
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。
索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数
索引的优缺点：
- 优势：可以快速检索，减少I/O次数，加快检索速度；根据索引分组和排序，可以加快分组和排序；
- 劣势：索引本身也是表，因此会占用存储空间，一般来说，索引表占用的空间的数据表的1.5倍；索引表的维护和创建需要时间成本，这个成本随着数据量增大而增大；构建索引会降低数据表的修改操作（删除，添加，修改）的效率，因为在修改数据表的同时还需要修改索引表
索引的实现方式：
- 哈希索引：哈希索引用索引列的值计算该值的hashCode，然后在hashCode相应的位置存储该值所在行数据的物理位置，因为使用散列算法，因此访问速度非常快，但是一个值只能对应一个hashCode，而且是散列的分布方式，因此哈希索引不支持范围查找和排序的功能。
- 全文索引：仅可用于MyISAM和InnoDB，针对较大的数据，非常的消耗时间和空间。对于文本的大对象，或者较大的CHAR类型的数据，如果使用普通索引，那么匹配文本前几个字符还是可行的，但是想要匹配文本中间的几个单词，那么就要使用LIKE %word%来匹配，这样需要很长的时间来处理，响应时间会大大增加，这种情况，就可使用时FULLTEXT索引了，在生成FULLTEXT索引时，会为文本生成一份单词的清单，在索引时及根据这个单词的清单来索引。
- B-Tree索引和B+Tree索引：采用这种方式，是充分考虑到了计算机读取数据时是按页读取，并且带有空间局部性原理(由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存)
  B-tree索引：可以使用二分搜索，时间复杂度在 $O(\log_d n)$
  - 为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据
  - B-Tree需要满足的条件:
    
    $d$ 为大于1的一个正整数，称为B-Tree的度
    
    $h$ 为一个正整数，称为B-Tree的高度
    
    每个非叶子节点由 $n-1$ 个 $key$ 和 $n$ 个指针组成，其中 $d\leq n\leq2d$
    
    每个叶子节点最少包含一个 $key$ 和两个指针，最多包含 $2d-1$ 个 $key$ 和 $2d$ 个指针，叶节点的指针均为null
    
    所有叶节点具有相同的深度，等于树高 $h$
    
    $key$ 和指针互相间隔，节点两端是指针
    
    一个节点中的 $key$ 从左到右非递减排列
    
    所有节点组成树结构
    
    每个指针要么为null，要么指向另外一个节点
    
    如果某个指针在节点node最左边且不为null，则其指向节点的所有 $key$ 小于 $v(key_1)$ ，其中 $v(key_1)$ 为node的第一个 $key$ 的值
    
    如果某个指针在节点node最右边且不为null，则其指向节点的所有 $key$ 大于 $v(key_m)$ ，其中 $v(key_m)$ 为node的最后一个 $key$ 的值
    
    如果某个指针在节点node的左右相邻 $key$ 分别是 $key_i$ 和 $key_{i+1}$ 且不为null，则其指向节点的所有 $key$ 小于 $v(key_{i+1})$ 且大于 $v(key_i)$
    b-tree结构示意图
  B+Tree索引: B-Tree的变种
  - 与B-Tree相比，B+Tree有以下不同点：
    
    每个节点的指针上限为2d而不是2d+1
    
    内节点不存储data，只存储key；叶子节点不存储指针
    
    B+Tree基础结构
    
    一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针，做这个优化的目的是为了提高区间访问的性能
    
    B+Tree优化结构
    
    由 $O(\log_d n)$ 知，d越大，性能越好，而出度的上限取决于节点内key和data的大小 $d_{max}=floor(page_{size}/(key_{size}+data_{size}+point_{size}))$ ,floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能

部分内容参考自：https://www.kancloud.cn/kancloud/theory-of-mysql-index/41856

MySql索引原理总结

猜你喜欢

热点阅读