数据库索引在平时的工作是必备的,怎么建好索引,怎么使用索引,可以提高数据的查询效率。而且在面试过程,数据库的索引也是必问的知识点,比如:
索引底层结构选型,那为什么选择B+树?
不同存储引擎的索引的体现形式有哪些?
索引的类型
覆盖索引是什么?
看着这些,能说出多少,理解多少呢?因此我们需要去探究其内在原理。
那索引是什么?
索引的目的为了加速检索数据而设计的一种分散存储(索引常常很大,属于硬盘级的东西,所以是分散存储)的数据结构,其原理以空间换时间。
快速检索的实现的本质是数据结构,通过不同数据结构的选择,实现各种数据快速检索,索引有哈希索引和B+树索引。
索引底层结构选型,那为什么选择B+树?
数据库索引底层选型归根到底就是为提高检索效率,那么就需要考虑几个问题:
NOTE: 考虑到磁盘IO是非常高昂的操作,计算机操作系统做了一些优化,当一次IO时,不光把当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区内,因为局部预读性原理告诉我们,当计算机访问一个地址的数据的时候,与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。
哈希表( Hash Table,散列表 )
哈希表是根据键(Key)而直接访问在内存存储位置的数据结构。
通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。虽然查询时间复杂度为O(1),但存在着碰撞问题,最坏情况会导致时间复杂急剧增加;
而且哈希表其只适合精准key(等于)检索,不适合范围式检索,范围检索就需要一次把所有数据找出来加载到内存,没有效率,因此不适合Mysql的底层索引的数据结构。
普通的二叉查找树
为了优化高效范围查询,且时间复杂度小,引入二叉查找树
二叉查找树的时间复杂度是 O(lgn),由于数据已排序好了,所以范围查询是可以高效查询,
但会存在的问题:左右子节点的深度可能相差很大,最极端的情况只有左子树或者右子树,此时查找的效率为O(n),检索性能急剧下降,因此也不适合Mysql的底层索引的数据结构。
平衡二叉树(AVL树)
为了优化二叉树左右子树深度相差太大的问题,我们引入了平衡二叉树,即左右子节点的深度差不超过1,平衡二叉树看来好像适合,实现了:
NOTE:上图中一个磁盘块,代表硬盘上的一个存储位置
但是我们还有一个最重要因素需要考虑,磁盘IO与预读,且数据库查询数据的瓶颈在于磁盘 IO,使用平衡二叉树根据索引进行查找时,每读一个磁盘块就进行一次IO,这样没有实现计算机的预读能力,导致检索效率下降,总结出平衡二叉树作为索引的问题
B+树
为了优化磁盘IO和预读,减少IO操作,条路太少了,那么换成多条路,那么会想到使用B树和B+树,但B树每个节点限制最多存储两个 key,也会造成IO操作过于频繁,因此优化思路为:尽可能在一次磁盘 IO 中多读一点数据到内存,那么B+树也该出场:
相对于B树,B+树的优势有:
索引的体现形式
索引在不同的存储引擎中体现形式步一样, 最常见的是:
聚集索引方式(InnoDB存储引擎)
InnoDB存储引擎中,索引和数据是存放在同一个文件的,属于聚集索引 。而且InnoDB会自动建立好主键 ID 索引树, 因此建表时要求必须指定主键的原因。
其中,主键索引(聚集索引)的叶子节点记录了数据,而不是数据的物理地址。辅助索引的叶子节点存放的是主键key。所以当利用辅助索引查找数据时,实际上查了两遍索引(辅助索引和主键索引):
非聚集索引方式(Myisam存储引擎)
Myisam存储引擎中,索引和数据是存放在两个文件中的,属于非聚集索引 。不管是主键索引还是辅助索引,其叶子节点都是记录了数据的物理地址。
MySQL的索引类型
MySQL索引可以分为:
唯一索引:
联合索引:
全文索引full text :用于搜索很长一篇文章的时候,效果最好。
其中,主要理解一下联合索引的问题,存储结构,查询方式。
联合索引
联合索引,多个列组成的索引叫做联合索引,单列索引是特殊的联合索引。其存储结构如下:
对于联合索引来说其存储结构只不过比单值索引多了几列,组合索引列数据都记录在索引树上,(不同的组合索引,B+树也是不同的),且存储引擎会首先根据第一个索引列排序后,其他列再依次将相等值的进行排序。
NOTE:叶节点第一排,按顺序排序好,第二列,会基于第一列排序好的,将第一列相等的再下一列再排序,依次类推。
联合索引查询方式,存储引擎首先从根节点(一般常驻内存)开始查找,然后再依次在其他列中查询,直到找到该索引下的data元素即ID值,再从主键索引树上找到最终数据。
而且联合索引其选择的原则:
最左前缀匹配原则
最左前缀匹配原则和联合索引的索引构建方式及存储结构是有关系的。根据上述理解分析,可以得出联合索引只能从多列索引的第一列开始查找索引才会生效,比如:
离散度
当索引中的一列离散度过低时,优化器可能直接不走索引,离散度计算方法:
覆盖索引
如果一个索引包含(或覆盖)所有需要查询的字段的值,称为覆盖索,即只需扫描索引而无须回表查询 。覆盖索引可减少数据库IO,将随机IO变为顺序IO,可提高查询性能。
对于InnoDB辅助索引在叶子节点中保存了行的主键值,所以如果辅助索引(包括联合索引)能够覆盖查询,则可以避免对主键索引的二次查询。比如:
- --创建联合索引
- create index name_phone_idx on user(name,phoneNum);
- --此时是覆盖索引,原因是根据name来查,命中索引name_phone_idx,
- --其关键字为name,phoneNum,本身就已经包含了查询的列。
- select name,phoneNum where name = "张三";
- --如果id为主键的话,此时也称作覆盖索引,原因:辅助索引的叶子节点存的就是主键
- select id,name,phoneNum where name = "张三";
总结
MySQL的索引有很多知识点要掌握,已学习了索引的底层存储结构,不同存储引擎中的索引体现,以及索引类型的基础原理知识分析,可以为后续的数据库优化提供理论知识的支撑,也会更好的理解优化方案。
手机会收集用户数据这件事情,大家或多或少都有所了解,无论 iOS 还是 Android ...
文章目录 Java基础语法三——运算符 一、算术运算符 1.基本四则运算符 1练习 2注...
本文转载自公众号读芯术(ID:AI_Discovery) 本文将指出一些常见但却总是被忽略的...
后台将富文本编辑器中的内容返回到前端时如果带上了标签,这时就可以利用这种方...
本地路径的创建 在做下载操作时,我们一般先把文件下载到本地指定的路径下,然后...
我们在使用MongoDB的时候,一个集合里面能放多少数据,一般取决于硬盘大小,只要...
XML Schema是定义XML的数据定义文件,以.xsd作为文件的扩展名。它也以被用来定义...
写在前面 本文涉及面较广,篇幅较长,阅读完需要耗费一定的时间与精力,如果你带...
原著:Jan Egil Refsnes 翻译:阿捷 五. XSL 的索引 如果我需要将元素的显示按一...
开展新项目 本文主要记录最近工作一个新项目从0-1的过程,主要记录3个节点,选型...