Thresh

索引是物理数据页存储，在数据文件中（InnoDB，ibd文件），利用数据页(page)存储。索引能够放慢检索速度，然而同时也会升高增删改操作速度，索引保护须要代价。

索引波及的理论知识：二分查找法、Hash和B+Tree。

二分查找法

二分查找法也叫作折半查找法，它是在有序数组中查找指定数据的搜索算法。

长处是等值查问、范畴查问性能优良毛病是更新数据、新增数据、删除数据保护老本高。

• 首先定位left和right两个指针
• 计算(left+right)/2
• 判断除2后索引地位值与目标值的大小比对
• 索引地位值大于目标值就-1，right挪动；如果小于目标值就+1，left挪动

 public static int binarySearch(int key, int... array) {        int low = 0;        int high = array.length - 1;        while (low <= high) {            int mid = low + (high - low) / 2;            if (key < array[mid]) {                high = mid - 1;            } else if (key > array[mid]) {                low = mid + 1;            } else {                return mid;            }        }        return -1;    }

Hash构造

Hash底层实现是由Hash表来实现的，是依据键值 <key,value> 存储数据的构造。
非常适合依据key查找value值，也就是单个key查问，或者说等值查问。

Hash索引能够不便的提供等值查问，然而对于范畴查问就须要全表扫描了。

Hash索引在MySQL中Hash构造次要利用在Memory(存储引擎 基于内存 很少用)原生的Hash索引 、InnoDB 自适应哈希索引。

InnoDB自适应哈希索引是为了晋升查问效率，InnoDB存储引擎会监控表上各个索引页的查问，当InnoDB留神到某些索引值拜访十分频繁时，会在内存中基于B+Tree索引再创立一个哈希索引，使得内存中的 B+Tree 索引具备哈希索引的性能，即可能疾速定值拜访频繁拜访的索引页。

InnoDB自适应哈希索引：在应用Hash索引拜访时，一次性查找就能定位数据，等值查问效率要优于B+Tree。

自适应哈希索引的建设使得InnoDB存储引擎能主动依据索引页拜访的频率和模式主动地为某些热点页建设哈希索引来减速拜访。
另外InnoDB自适应哈希索引的性能，用户只能抉择开启或敞开性能，无奈进行人工干预。

show engine innodb status \G; show variables like '%innodb_adaptive%';

B+Tree构造

MySQL数据库索引采纳的是B+Tree构造，在B-Tree构造上做了优化革新

B-Tree构造

• 索引值和data数据分布在整棵树构造中
• 每个节点能够寄存多个索引值及对应的data数据
• 树节点中的多个索引值从左到右升序排列

B树的搜寻：从根节点开始，对节点内的索引值序列采纳二分法查找，如果命中就完结查找。没有命中会进入子节点反复查找过程，直到所对应的的节点指针为空，或曾经是叶子节点了才完结。

B+Tree构造

• 非叶子节点不存储data数据，只存储索引值，这样便于存储更多的索引值
• 叶子节点蕴含了所有的索引值和data数据
• 叶子节点用指针连贯，进步区间的拜访性能

相比B树，B+树进行范畴查找时，只须要查找定位两个节点的索引值，而后利用叶子节点的指针进行遍历即可。而B树须要遍历范畴内所有的节点和数据，显然B+Tree效率高。

聚簇索引和辅助索引

聚簇索引和非聚簇索引：B+Tree的叶子节点寄存主键索引值和行记录就属于聚簇索引；如果索引值和行记录离开寄存就属于非聚簇索引。

主键索引和辅助索引：B+Tree的叶子节点寄存的是主键字段值就属于主键索引；如果寄存的是非主键值就属于辅助索引（二级索引）。

在InnoDB引擎中，主键索引采纳的就是聚簇索引构造存储。

聚簇索引（汇集索引）
聚簇索引是一种数据存储形式，InnoDB的聚簇索引就是依照主键程序构建 B+Tree构造。B+Tree的叶子节点就是行记录，行记录和主键值紧凑地存储在一起。 这也意味着 InnoDB 的主键索引就是数据表自身，它按主键程序寄存了整张表的数据，占用的空间就是整个表数据量的大小。通常说的主键索引就是汇集索引。

辅助索引
InnoDB辅助索引，也叫作二级索引，是依据索引列构建 B+Tree构造。但在 B+Tree 的叶子节点中只存了索引列和主键的信息。二级索引占用的空间会比聚簇索引小很多， 通常创立辅助索引就是为了晋升查问效率。一个表InnoDB只能创立一个聚簇索引，但能够创立多个辅助索引。

非聚簇索引
与InnoDB表存储不同，MyISAM数据表的索引文件和数据文件是离开的，被称为非聚簇索引构造。