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 数据表的索引文件和数据文件是离开的，被称为非聚簇索引构造。