数据库索引数据结构

什么是索引

索引是一个有序的数据结构

优缺点

优点：

• 可以快速检索，减少I/O次数，加快检索速度；
• 根据索引分组和排序，可以加快分组和排序；

缺点：

• 索引本身也是表，因此会占用存储空间，一般来说，索引表占用的空间的数据表的1.5倍；
• 索引表的维护和创建需要时间成本，这个成本随着数据量增大而增大；
• 构建索引会降低数据表的修改操作（删除，添加，修改）的效率，因为在修改数据表的同时还需要修改索引表；

分类

按类型分：

• 主键索引；
• 唯一索引；
• 普通索引；
• 全文索引；
• 组合索引；

按数据结构分：

• BTree索引；
• B+Tree索引；
• 哈希索引；
• 全文索引；

哈希索引

只有memory（内存）存储引擎支持哈希索引，哈希索引用索引列的值计算该值的hashCode，然后在hashCode相应的位置存执该值所在行数据的物理位置，因为使用散列算法，因此访问速度非常快，但是一个值只能对应一个hashCode，而且是散列的分布方式，因此哈希索引不支持范围查找和排序的功能。

全文索引

FULLTEXT（全文）索引，仅可用于MyISAM和InnoDB，针对较大的数据，生成全文索引非常的消耗时间和空间。对于文本的大对象，或者较大的CHAR类型的数据，如果使用普通索引，那么匹配文本前几个字符还是可行的，但是想要匹配文本中间的几个单词，那么就要使用LIKE %word%来匹配，这样需要很长的时间来处理，响应时间会大大增加，这种情况，就可使用时FULLTEXT索引了，在生成FULLTEXT索引时，会为文本生成一份单词的清单，在索引时及根据这个单词的清单来索引。

A. 5.6版本前的MySQL自带的全文索引只能用于MyISAM存储引擎，如果是其它数据引擎，那么全文索引不会生效。5.6版本之后InnoDB存储引擎开始支持全文索引
B. 在MySQL中，全文索引支队英文有用，目前对中文还不支持。5.7版本之后通过使用ngram插件开始支持中文。

BTree索引和B+Tree索引

BTree索引

BTree的数据结构是平衡多叉树，节点包含的数据数称为度。

BTree的特点：

• 每个叶子节点的高度一样（通常为3-5）；
• 每个叶子节点有N-1个key和N个指针组成；
• 叶子节点指正都为null；
• 非叶子结点的key都是[key,data]二元组，其中key表示作为索引的键，data为键值所在行的数据；

BTree

BTree结构可以使用二分查找的查找方式，查找复杂度为h*log(n)。

B+Tree索引

B+Tree索引是BTree的一个变种。

B+Tree

B+Tree与BTree的区别：

• B+Tree中的非叶子结点不存储数据，只存储键值；
• B+Tree的叶子结点没有指针，所有键值都会出现在叶子结点上，且key存储的键值对应data数据的物理地址；
• B+Tree的每个非叶子节点由n个键值key和n个指针point组成；

B+Tree对比BTree的优点

磁盘读写代价更低

磁盘一次读取一页数据（4k），非叶子节点不包含原始数据，能够存储跟多的数据，这样可以保证树的高度更低，I/O操作更少。

存储引擎的设计专家巧妙的利用了外存（磁盘）的存储结构，即磁盘的最小存储单位是扇区（sector），而操作系统的块（block）通常是整数倍的sector，操作系统以页（page）为单位管理内存，一页（page）通常默认为4K，数据库的页通常设置为操作系统页的整数倍，因此索引结构的节点被设计为一个页的大小，然后利用外存的“预读取”原则，每次读取的时候，把整个节点的数据读取到内存中，然后在内存中查找，已知内存的读取速度是外存读取I/O速度的几百倍。

查询速度更稳定

由于B+Tree非叶子节点不存储数据（data），因此所有的数据都要查询至叶子节点，而叶子节点的高度都是相同的，因此所有数据的查询速度都是一样的，均衡的。

带顺序索引的B+Tree

很多存储引擎在B+Tree的基础上进行了优化，添加了指向相邻叶节点的指针，形成了带有顺序访问指针的B+Tree，这样做是为了提高区间查找的效率，只要找到第一个值那么就可以顺序的查找后面的值。

B+Tree

聚簇索引和非聚簇索引

MySQL中最常见的两种存储引擎分别是MyISAM和InnoDB，分别实现了非聚簇索引和聚簇索引。

• 聚簇索引的解释是: 聚簇索引的顺序就是数据的物理存储顺序
• 非聚簇索引的解释是: 索引顺序与数据物理排列顺序无关

在索引的分类中，我们可以按照索引的键是否为主键来分为“主索引”和“辅助索引”，使用主键键值建立的索引称为“主索引”，其它的称为“辅助索引”。因此主索引只能有一个，辅助索引可以有很多个。

非聚簇索引（MyISAM）

• MyISAM存储引擎采用的是非聚簇索引，非聚簇索引的主索引和辅助索引几乎是一样的，只是主索引不允许重复，不允许空值，他们的叶子结点的key都存储指向键值对应的数据的物理地址；

• 非聚簇索引的数据表和索引表是分开存储的；

• 非聚簇索引中的数据是根据数据的插入顺序保存。因此非聚簇索引更适合单个数据的查询。插入顺序不受键值影响；

• 只有在MyISAM中才能使用FULLTEXT索引。(mysql5.6以后innoDB也支持全文索引)；

聚簇索引（InnoDB）

• 聚簇索引的主索引的叶子结点存储的是键值对应的数据本身，辅助索引的叶子结点存储的是键值对应的数据的主键键值。因此主键的值长度越小越好，类型越简单越好；

• 聚簇索引的数据和主键索引存储在一起；

• 聚簇索引的数据是根据主键的顺序保存。因此适合按主键索引的区间查找，可以有更少的磁盘I/O，加快查询速度。但是也是因为这个原因，聚簇索引的插入顺序最好按照主键单调的顺序插入，否则会频繁的引起页分裂，严重影响性能；

• 在InnoDB中，如果只需要查找索引的列，就尽量不要加入其它的列，这样会提高查询效率；

对比

• 使用主索引的时候，更适合使用聚簇索引，因为聚簇索引只需要查找一次，而非聚簇索引在查到数据的地址后，还要进行一次I/O查找数据；

• 因为聚簇辅助索引存储的是主键的键值，因此可以在数据行移动或者页分裂的时候降低成本，因为这时不用维护辅助索引。但是由于主索引存储的是数据本身，因此聚簇索引会占用更多的空间；

• 聚簇索引在插入新数据的时候比非聚簇索引慢很多，因为插入新数据时需要检测主键是否重复，这需要遍历主索引的所有叶节点，而非聚簇索引的叶节点保存的是数据地址，占用空间少，因此分布集中，查询的时候I/O更少，但聚簇索引的主索引中存储的是数据本身，数据占用空间大，分布范围更大，可能占用好多的扇区，因此需要更多次I/O才能遍历完毕；