MySQL（⼋）：索引，java程序设计案例教程课后答案吕林涛
OLTP与OLAP
不同应⽤中B+树索引的使⽤
联合索引
覆盖索引
INDEX HINT
Multi-Range Read
Index Condition Pushdown
T树索引
T树概述
T树的查、插⼊和删除操作
T树的旋转
哈希索引（索引不再是B+树，⽽是⼀个散列表）
散列表
InnoDB存储引擎中的散列算法
⾃适应哈希索引
缓冲池、顺序读取和顺序读取
根据存储介质的不同，可以将数据库分为基于磁盘的数据库系统、基于内存的数据库系统，以及混合型数据库系统。基于磁盘的数据库系统是最为常见的⼀种关系型数据库，⽐如MySQL、SQL Server。随着内存的使⽤不断增加，基于内存的数据库系统也变得⼗分流⾏了，⽽混合型数据库系统就是将上述两种数据库的有点进⾏了结合。
毫⽆疑问，基于内存的数据库系统是最快的，因为数据库不需要对磁盘进⾏操作，磁盘的速度要远远慢于内存的速度，因此基于磁盘的数据库系统⼀斑都有缓冲池，即⼀块内存区域，其作⽤是从磁盘上读取的指定⼤⼩数据——称为页或块，放⼊缓冲池中，当再次读取的时候，数据库会⾸先判断该页是否在缓
冲池中，如果在的话，会直接从缓冲池中读取缓冲池中的页，如果不在则读取磁盘上的页（读取了就会放⼊缓冲池中）。⽽对于写的操作，数据库将页读⼊缓冲池中，然后在缓冲池中对页进⾏修改，修改完成的页⼀般被异步地写⼊磁盘中（异步即开启另⼀个线程去写，不影响当前的使⽤，同步是要完成当前的动作，才能开启下⼀个动作）。
对于缓冲池的维护⼀般采⽤LRU算法，由此可见，缓冲池的⼤⼩决定了数据库的性能，若数据库中的数据可以完全存放于缓冲池中，则可以认为这时的数据库是最优的，除了同步/异步的写磁盘的操作外，所有其他操作都可以在内存中完成。
对于MySQL数据库系统，由于其有着各种不同的存储引擎，因此其缓冲池是基于存储引擎的，也就是说每个存储引擎都有⾃⼰的缓冲池。对于MyISAM存储引擎来说，变量key_buffer_size决定了缓冲池的⼤⼩，对于InnoDB存储引擎来说，变量innodb_buffer_pool_size决定了缓冲池的⼤⼩。
现在我们来了解⼀下读取页（磁盘储存数据的单位）的⽅式
总共有2种⽅式，第⼀种是顺序读取，顺序读取是指按顺序地读取磁盘上的页，第⼆种是随机读取，随机读取并不是指随机去读取，⽽是指访问的页并不是连续的，即需要磁盘的磁头不断移动（传统的机械硬盘是由磁头、磁道、扇区、柱⾯组成的，读取时需要通过磁头的移动来定位数据，这个时间称为寻道时间）。这⾥需要注意的是，这⾥的顺序是指逻辑上的顺序（即获取页中的数据，数据的先后），在物
理上不可能保证所有的数据都是顺序的（即页在磁盘中的分布都是按顺序来的），⽽为了保证顺序，数据库存储引擎⼀般都是根据区来管理页，例如在InnoDB存储引擎中的⼀个区是64( 2 6 2^6 26)个页，因此在顺序读取数据库时，可以保证这64个页是连续的，⽽区与区之间的页，可能连续也可能不连续（⽐如某个表数据需要4页的存储空间，然后这个区只剩下3页，那么是明显不够的，需要另⼀个区再提供⼀页，那么这两个区的数据就连续了）
B+树索引
B+树的索引的本质就是B+树在数据库中的实现，⽽B+树索引在数据库中的⼀个特点就是⾼扇出性（就是结点可以放多个数据，每个数据⼜看作⼀个⼩结点，每个⼩结点的下⼀层⼜可以放左右两个结点，⽐如⼀个4-结点，那么这4-结点的⼦结点就有8个），例如在InnoDB存储引擎中，每个页的⼤⼩为16KB（页在B+树的体现，就是B+树的叶⼦结点，因为页是存储数据的，B+树只有叶结点有数据，注意这⾥的叶结点也是什么M-结点的，所以⼀个页是有多⾏数据的，也就是多个data，16KB也就⼤概16个结点），因此树的⾼度⼀般都在2~4层。
这意味着使⽤索引进⾏⼀次查，顶多需要2到4次的IO操作（访问磁盘，或者访问缓存区）。
B+树索引可以分为聚集索引和辅助索引（即⾮聚集索引），但是这两者本⾝本质都与B+树结构⼀样，区别仅仅在于所存放的数据不同。
InnnoDB的B+树索引
InnoDB的存储引擎索引组织表，也就是说数据⽂件本⾝（页和块）就是按照B+树⽅式存放数据的。其中，B+树的键值为主键，若在建⽴时没有显⽰地指定主键，则InnoDB存储引擎会⾃动创建⼀个6字节的列作为主键，. 如果没有主键被定义，那么该表的第⼀个唯⼀⾮空索引被作为聚集索引（跟Redis差不多，⾃动创建⼀个UUID，但不同的是这⾥创建的是ROWID，⽽且不像UUID⼀样是⽆序的！因为⽆序会在结点中间进⾏插⼊，那么就要进⾏维护，有序的话直接在尾巴后⾯插⼊即可），因此在InnoDB存储引擎中，可以将B+树索引分为聚集索引（显⽰地⾃定义主键）和辅助索引（针对没有显⽰⽣成主键，⾃动⽣成主键的情况），⽆论是何种索引，每个页的⼤⼩都为16KB（限定了B+树的叶⼦结点最多⽅能放多少个数据），且不能更改。
两种索引
聚集索引是根据主键创建的⼀棵B+树，聚集索引的叶⼦结点放了表中的所有记录（也就是数据），辅助索引是根据索引键（⾃动⽣成的索引值）创建的⼀棵B+树，与聚集索引不同的是，其叶⼦结点仅仅存放索引键值（仅仅存放主键值），以及该索引键值指向的主键（这⾥是⾃动⽣成的主键）。也就是说，如果通过辅助索引来查数据，那么当到辅助索引的叶⼦结点后，很有可能还需要根据主键值查聚集索引来得到数据，这种查⽅式⼜称为书签查（因为⾥⾯除了有辅助索引的索引值和主键值外【对应
为k,v】，还有⼀个值，存储的是聚集索引的位置，这个值称为书签），因为辅助索引不包含⾏⽬录的所有数据，这就意味着每页可以存放更多的键值，因此其⾼度⼀般都要⼩于聚集索引（但效率不⼀定⾼，因为到真实的数据，需要去搜索对应的聚集索引的B+树）。
MyISAM的B+树索引
MyISAM存储引擎其实更像⼀张堆表，所有的⾏数据都存放于MYD⽂件中，其B+树索引都是辅助索引，存放于MYI⽂件中。PRIMARY KEY索引（主键索引）和其他索引不同之处在于其必须是唯⼀的，并且不可以为NULL值，其索引页的⼤⼩默认为1KB（InnoDB是
16KB），同样是不可以进⾏调整的（MySQL的所有引擎都不可以对索引页进⾏⼤⼩调整，但可以调整缓冲池⼤⼩）。此外，与InnoDB存储引擎不同的是，因为没有聚集索引，其索引结点存放的键值不是主键值（相当于没有主键，InnoDB只要定义了主键，就会⽣成聚集索引），⽽是MYD⽂件中的物理位置（直接映射磁盘的真实位置）。
Cardinality
什么是Cardinality?
并不是所有在查询条件中出现的列都需要添加索引，对于什么时候添加B+树索引，⼀般的经验是，在访
问表中很少⼀部分⾏时使⽤B+树索引才有意义，⽐如性别字段、地区字段、类型字段，他们可取值的范围很⼩，称为低选择性。
下⾯举个栗⼦
SELECT * FROM student WHERE sex = ‘M’;
这句SQL是查学⽣表中的男⽣，sex的字段⾥⾯只有M和F，因此上述的SQL得到的结果⼤概是50%左右数据（假设男⼥⽐例为1：1），这时添加B+树是完全没有必要的。相反，如果某个字段的取值范围很⼴，⼏乎没有重复，即是⾼选择性的（⽐如⽤户表的id），那么此时使⽤B+树索引是最适合的，例如姓名字段，基本上在每⼀个应⽤中都不允许出现重名。
那要怎样查看索引是否是⾼选择性呢？这⾥可以通过使⽤SHOW INDEX语句中的Cardinality列来观察，Cardinality值是⾮常关键的，表⽰索引中唯⼀只记录数量的遇预估值。这⾥需要注意的是，Cardinality只是⼀个预估值，⽽不是⼀个准确值，⽤户也不可能得到⼀个准确的值。在实际应⽤中，Cardinality/n_rows_in_table应尽可能接近1，如果⾮常⼩，那么就要考虑是否需要重建索引了
EXPLAIN SELECT * FROM account WHERE id = 500;
这⾥id字段有个主键索引，这时进⾏查，并且查id=500，得到的执⾏计划如图所⽰
可以看到使⽤了id这个索引，符合前⾯提到的⾼选择性，只选取表中很少的⾏原则
B+树索引的使⽤
OLTP与OLAP
OLTP主要执⾏基本的、⽇常的事务处理，⽐如在银⾏进⾏存取⼀笔钱，就是⼀个事务交易，它的特点有
1. 实时性要求⾼
2. 查询的数据量不是很⼤
3. 交易⼀般是确定的，所以OLTP是对确定性的数据进⾏存取
4. 并发性要求⾼，并且严格要求事务的完整性、安全性
OLAP是数据仓库系统的主要应⽤，典型的应⽤就是复杂的动态报表系统，OLAP的特点⼀般有
1. 实时性要求不是很⾼，很多应⽤最多⼀天只查⼀次
2. 数据量⼤，因为OLAP⽀持动态查询，⽤户要通过对很多数据的统计才能得到想要的信息
3. 终点在于决策⽀持，所以查询⼀般是动态的，也就是说允许⽤户随时提出查询的要求
不同应⽤中B+树索引的使⽤
OLTP应⽤中，⽤户只要查询⼀⼩部分的数据，⼀般都在10条记录以下，甚⾄⼤多数情况只有1条（⽐如根据主键去查⽤户信息，根据订单号取得订单信息，这些都是典型的OLTP应⽤的查询语句），在这种情况下，建⽴B+树索引后，对该索引的使⽤应该只是通过该索引获取⼩部分的数据，这时建⽴B+树索引才有意义的，否则即使建⽴了，优化器也可能选择不适⽤索引。
但对于OLAP应⽤，情况就⽐较复杂了，不过总的来说，OLAP都需要访问表中⼤量的数据，并根据这些数据来产⽣查询的结果，⼀般不太需要索引，但是对于复杂查询，如果需要涉及多张表之间的联接操作，这时索引的添加可能才会有意义（联接操作，减少了数据量）
联合索引
联合索引是指对表上的多个列进⾏索引。
下⾯举个栗⼦
CREATE TABLE t(
a INT,
b INT,
PRIMARY KEY(a),
KEY idx_a_b(a,b)
)ENGINE=Innodb,charset=utf8;
上⾯的SQL语句定义了a为主键索引，然后⼜定义了(a,b)为联合索引
下⾯我们来分析⼀下联合索引有什么⽤
按上⾯的SQL，⽣成的索引如下⾯所⽰，对应分别为(a,b)
我们可以看到与前⾯的聚集索引或者⾮聚集索引的B+树没什么区别，除了联合索引的键值数量不是1，⽽是⼤于或者等于2。
因此，对于WHERE a = “xxx” and b = “xxx”；的SELECT语句显然是可以使⽤的，对于单个列的a列查询，即WHERE a = "xxx"的SELECT语句也是可以使⽤的，但对于b列的查询，就不可以使⽤了，因为我们可以看到叶⼦节点上的b值，并不是按顺序进⾏排列的，因此对b列的查询不可以使⽤联合索引
联合索引的另⼀个好处就是可以对第⼆个键值进⾏排序，下⾯举个栗⼦
CREATE TABLE buy_log(
userid INT UNSIGNED NOT NULL,
buy_date DATE
)ENGINE=INNODB;
INSERT INTO buy_log VALUES(1,‘2009-01-01’);
INSERT INTO buy_log VALUES(2,‘2009-01-01’);
INSERT INTO buy_log VALUES(3,‘2009-01-01’);
INSERT INTO buy_log VALUES(1,‘2009-02-01’);
INSERT INTO buy_log VALUES(3,‘2009-02-01’);
INSERT INTO buy_log VALUES(1,‘2009-03-01’);
INSERT INTO buy_log VALUES(1,‘2009-04-01’);
ALTER TABLE buy_log ADD KEY(userid);
ALTER TABLE buy_log ADD KEY(userid,buy_date);
然后执⾏下列的语句
EXPLAIN SELECT * FROM buy_log WHERE userid = 2;
优化器选择了使⽤单个列的聚集索引，因为这个索引的叶⼦结只有1个键值，也就是这个结点能存放更多的键值（⼀页有16KB，然后⼀个叶⼦结点就是⼀页）
【⼀线⼤⼚Java⾯试题解析+后端开发学习笔记+最新架构讲解视频+实战项⽬源码讲义】
mg-blog.csdnimg/20210423230048949.png#pic_center)
可以看到选择器选择了userid_2这个索引，也就是联接索引，因为在这个联合索引中，buy_date是已经排序好了，如果使⽤这个索引进⾏取出数据，就⽆需再对buy_date做⼀次额外的排序操作（可以看到在Extra列上，只有使⽤了index scan和index，并没有using filesort）。
强制使⽤单⼀列来索引的话
EXPLAIN SELECT * FROM buy_log FORCE INDEX(userid) WHERE userid = 2 ORDER BY buy_date DESC LIMIT 3;
可以看到Extra⾥拥有using filesort，即表明了需要额外的⼀次排序才能完成查询，⽽这次排序明显是对buy_date进⾏排序。
覆盖索引
InnoDB存储引擎⽀持覆盖索引，或称为索引覆盖，即从辅助索引中就可以得到查询记录，⽽不需要查询聚集索引中的记录（⼀般辅助索引⾥⾯存放索引键值，然后还要根据索引键值去查聚集索引），即叶
⼦结点已经包含了想要的数据，不需要再去聚集索引中完整的数据，引⽤覆盖索引的好处是辅助索引不包含整⾏记录的所有信息，故其⼤⼩会远⼩于聚集索引，因此可以减少IO操作。
对于InnoDB存储引擎的辅助索引⽽⾔，叶⼦结点是包含主键信息的，所以页中存储的内容⼤概是(primary key 1,primary key 2…,key 1,key 2)这样的数据，所以下列的SQL语句都可以直接查询这些数值出来，⽽不需要额外去聚集索引
SELECT key2 FROM table WHERE key 1 = xxx;
sql查询面试题及答案
SELECT primary key2,key2 FROM table WHERE key 1 = xxx;
SELECT primary key1,key2 FROM table WHERE key1 = xxx;
SELECT primary key1,primary key2,key1,key2 FROM table WHERE key1 = xxx;
覆盖索引的另⼀个好处就是，辅助索引会⼩于聚集索引（由于每条⾏数据的列不全），可以减少IO操作。
⽤上⾯的bug_log表为例
EXPLAIN SELECT COUNT(*) FROM buy_log;
Using index其实就是覆盖索引操作
此外，⼀般来说对于诸如(a,b)这样的联合索引，⼀般不可以选择b列作为查询条件，但如果是对于统计操作，会选择覆盖索引来进⾏优化。INDEX HINT
MySQL数据库⽀持INDEX HINT（索引提⽰），显⽰地告诉优化器使⽤哪个索引，下⾯这两种情况可能需要使⽤到INDEX HINT。
MySQL数据库的优化器错误地选择了某个索引（这种情况⽐较少见，优化器在绝⼤部分情况下⼯作都是正确的），导致SQL语句运⾏得很慢。这时候就需要强制使⽤正确的索引
某SQL语句可以选择的索引⾮常多，这时优化器选择执⾏计划时间的开销可能会⽐较⼤，当⼤于执⾏SQL本⾝的时候，就需要强制使⽤某个索引了。
如何使⽤INDEX HINT
USE INDEX(列)
下⾯举个栗⼦
⾸先我们来介绍⼀下mySQL的⼏种key
1、key 是数据库的物理结构，它包含两层意义和作⽤，
⼀是约束（偏重于约束和规范数据库的结构完整性），
⼆是索引（辅助查询⽤的）。
2、primary key 有两个作⽤，
⼀是约束作⽤（constraint），⽤来规范⼀个存储主键和唯⼀性，
⼆是在此key上建⽴了⼀个主键索引（在InnoDB上就是聚集索引）；
还有⼀点要注意的是primary key拥有⾃动定义的unique约束，也就是唯⼀
3、unique key 也有两个作⽤，
⼀是约束作⽤（constraint），规范数据的唯⼀性，
⼆是在这个key上建⽴了⼀个唯⼀索引；