数据库索引

索引的本质

索引是帮助MySQL高效获取数据的排好序的数据结构

• 索引的数据结构

1. 二叉排序树
2. 红黑树(二叉平衡树)
3. Hash表:对范围查找的支持很差
4. B-Tree

• 例子

  
  image.png
  

  图1展示一种可能的索引方式。左边是数据表，一共两列七条记录，最左边的是数据记录的物理地址(逻辑上相邻的记录在磁盘上不一定是物理相邻的)。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点包含索引键值和一个指向对应数据记录物理地址的指针，这样可以运用二叉查找在O(log2)的时间复杂度获取相应数据。

B-Tree

定义一条数据记录为一个二元组[key,data],其中key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。

• 性质
  d为大于1的一个正整数，称为B-Tree的度
  h为一个正整数，称为B-Tree的高度
  每个非叶子节点由n-1个key和n个指针组成，其中d≤n≤2d
  每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，页节点的指针均为null。
  所有叶节点具有相同的深度，等于树高h。
  key和指针互相间隔，节点两段是指针
• 叶节点具有哦相同的深度，叶节点的指针为空
• 所有索引元素不重复

• 节点中的数据索引从左到右递增排序

  
  image.png

B+Tree

B-Tree有许多变种，其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构

image.png

带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行优化，增加了顺序访问指针

image.png

如图所示，在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，从而极大提高区间查询效率。

从计算机组成原理分析B-/+Tree作为索引的理论依据

索引不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。索引查找过程会产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的复杂度。也就是说索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
B-Tree每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐就实现一个node只需一次I/O。B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存)，复杂度为O(h)=O(logdN)。一般实际应用中，出度d非常大，故h非常小。所以用B-Tree作为索引结构效率非常高。
而红黑树这种结构，h明显要深很多。由于逻辑上很近的节点(父子)物理上可能很远，无法利用局部性，所有红黑树的I/O复杂度也为O(h)，效率明显比B-Tree差很多。

MySQL索引实现

存储引擎用来形容表的，

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。如图设表共有三列，假设以Col1为主键，下图为一个MyISAM表的主索引。可以看出MyISAM的索引文件仅仅保存数据记录的地址。

image.png

在MyISAM中，主索引和辅助索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。若以Col2上建立一个辅助索引，则此索引的结构如下图所示:

image.png

同样是一颗B+Tree,data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的，即索引和数据不在一个文件中。

InnoDB索引实现

InnoDB也使用B+Tree作为索引结构。具体实现方式和MyISAM完全不同。第一个重大区别是InnoDB的数据文件本身就是索引文件。而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按照B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

• InnoDB存储表只有两个文件.frm和.ibd(index+data)

  
  image.png
  

  可以看出叶节点包含完整的数据记录，这种索引叫做聚集索引。因为
  InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键(MyISAM可以没有)，如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MysqL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
  第二个与MyISAM索引不同的是InnoDB的辅助索引data域存储相应记录主键的值而不是地址，换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，在col3上定义一个辅助索引:

  
  image.png
  以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引:第一遍检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

常见问题

• 问题1
  聚集索引:索引和数据聚集在一个文件中，索引和数据放在ibd中，查找只需要一次。
  非聚集索引:索引和数据不聚集一个文件中，即索引放在MYI ，数据放在MYD中，查找需要两次。
  MyISAM存储表有三个文件.frm、.MYD、.MYI
• 问题2:为什么InnoDB表必须有主键，并且推荐使用整型的自增主键?
  InnoDB必须有主键，即使不手动设置主键，mysql数据库也会默认加一列主键。
  uuid和int区别:

1. 比较速度上:uuid是一串字符串，比较起来没有整数比较那么简单
2. 在内存的占用上:uuid会占用更多的内存
   自增
   减少分裂的可能性

• 问题3:联合索引的底层存储结构?
  分库分表用雪花算法(自增主键)，redis也可以。

索引使用策略及优化

MySQL的优化主要分为结构优化和查询优化。