mysql索引


B-Tree

平衡多路查找树,目前大多数数据库文件查找系统都采用B-Tree或B+Tree作为索引结构

基本的数据结构:二元组tuple(key, data),key为记录的键值,data为除键值外的数据(主索引中data包括了数据的完整记录,辅助索引中存储主键)

每个节点包括指针pointer和key, 互相间隔,key从左到右非递减排列,节点两端是指针

B-Tree的度为非根节点最少拥有的子女节点数量,非叶子节点d<=key<=2n,叶子节点2<=key<=2d

B-Tree数据结构

B-Tree的插入删除

采用自增长字段作为主键,插入数据时,只需要按顺序插入当前索引节点的后面,如果一页写满,则开辟新的一页。形成一个紧凑的数据结构,近似顺序填满。

如果采用自定义的字段作为主键,字段值随机,每次新插入一条数据,插入到索引结构中间某位置,导致后续数据频繁的移动分页。

B+Tree

Mysql普遍使用B+Tree 实现索引结构 每个节点上指针上限为2d,比B-Tree少了一个左指针 内节点不存储data,只存储key,叶子节点不存储指针

3.png-12.2kB

B+Tree比更适合实现外存储索引结构

一般在数据库系统或文件系统中,增加了顺序访问指针。每个叶子节点增加一个指向相邻叶子节点的指针,提高了区间访问性能。可以顺着叶子节点和叶子节点之间指针顺序一次访问到所有数据节点。

mysql索引使用 B-Tree instead of Red-Black Tree

局部性原理与磁盘预读

数据库索引文件磁盘存放,磁盘存取速度远远低于主存,为了提高效率,尽量减少磁盘I/O

磁盘每次读取都会预读,向后读取一定长度的数据存入内存(局部性原理)。预读长度为页的整数倍。

当一个数据被用到时,其附近的数据也通常会马上被使用。 程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率.预读的长度一般为页(page)的整倍数。

MySQL(默认使用InnoDB引擎),将记录按照页的方式进行管理,每页大小默认为16K(这个值可以修改).linux 默认页大小为4K

B-Tree索引性能分析

每次新建节点,直接申请一个页的空间,保证一个节点物理上也存储在一个页里,加上计算机存储分配都是按页对齐,一个node只需要一次I/O就可以完全载入。

一个度为d,N个key,树高h<=logd((N+1)/2),检索一个key,查找节点的渐进复杂度为O(logdN),B-Tree的出度d特别大,一般大于100,因此h<=3

红黑树结构,树高h深很多,逻辑上相近的节点物理上可能很远,无法利用局部特性,I/O渐进复杂度也为O(h)。

B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小:

dmax=floor(pagesize/(keysize+datasize+pointsize))

floor表示向下取整。由于B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。

mysql InnoDB 索引建立

使用B+Tree作为索引结构。

MyISAM索引文件和数据文件是分离的,索引文件仅记录数据记录的地址。InnoDB数据文件本身就是索引文件。B+Tree树的叶子节点的data保存了完整的数据记录。索引的key是数据表的主键,InnoDB表数据文件本身就是主索引,聚集索引

10.png-15.6kB

InnoDB辅助索引叶子节点的data域存储的是主键值而不是地址。聚集索引的这种实现方式使得按主键的搜索效率很高,但是辅助索引需要经过两遍索引:

在使用InnoDB存储引擎,不建议使用过长的字段作为主键。辅助索引的data域存储的主键,引用主索引,过长的主索引会使得辅助索引过大。

同时,使用单调字段作为主键,,非单调的主键会造成插入新纪录时数据文件为了维持B+Tree特性而频繁分裂调整,十分低效。

索引使用策略优化

联合索引:有序元组<a1, a2, a3, …… , an>,索引之间的顺序是严格定义好的。

  1. 全列匹配:按照主索引中的所有列进行精确匹配时,索引可以被用到。where字句顺序颠倒,Mysql查询优化器会自动调整

  2. 最左前缀匹配: 查询条件精确匹配索引从左到右的一个或几个列时,可以用到索引,但是只用到一部分。如果不是从索引的最左第一列开始,无法用到索引

  3. 索引的中间某列未提供:只匹配按顺序的前几列,缺失列和缺失列之后的索引列未引用
    • 建立辅助索引:将查询的条件列另外建立辅助索引
    • 使用隔离列:将缺失的列条件补上,miss_column in (all values of miss_column),适用于缺失列的值不多的情况,否则要建立辅助索引
  4. 匹配某列的前缀字符串:like关键字,可以用到索引

  5. 范围查询:可以用到索引,但是范围列后面的列无法用到索引,索引最多用于一个范围列

  6. 索引列用到函数或表达式无法使用索引

索引的选择: 虽然索引加快了存储速度,但是索引文件本身要消耗存储空间,同时会加重插入删除和修改的负担。运行时也要消耗资源维护索引。

表的记录较少,没必要索引,全表扫描就好,分界线为2000左右。

索引列的选择性较低:不重复的索引值与表记录总数的比值,选择性越高索引价值越大

参考阅读:

MySQL索引背后的数据结构及算法原理

由 B-/B+ 树看 MySQL 索引结构