04|04 | 深入浅出索引（上）有问题未解答
SQL 查询慢，加索引，提高数据查询效率，表目录
索引的常见模型
（1）哈希表：值放数组，哈希函数 key 换算成确定位置， value 放这，如key冲突，拉出链表。
身份证信息和姓名的表，根据身份证号查找名字：
文章图片
图 1 哈希表示意图 User2 和 User4 根据身份证号算出来值都是 N，后面还跟链表。
查 ID_card_n2 对应名字：将 ID_card_n2 通过哈希函数算出 N；按顺序遍历，找到 User2。
ID_card_n 不是递增，增加快，查询慢。适用于只有等值查询，如Memcached 及其他一些 NoSQL 引擎。
（2）有序数组：
等值、范围查询优秀。更新成本高。适用于静态存储引擎
文章图片
图 2 有序数组示意图 身份证号没重复，递增的保存。ID_card_n2 二分法快速得到 O(log(N))。
[ID_card_X,ID_card_Y] 区间的 User，二分法找到 ID_card_X（如不存在 ID_card_X，就找到大于 ID_card_X 的第一个 User），向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，退出循环。
（3）二叉搜索树 
文章图片
图 3 二叉搜索树示意图 左儿子小于父节点，父节点又小于右儿子。查 ID_card_n2 的话，按照 UserA ->
UserC -> UserF -> User2查询O(log(N))。维持 O(log(N)) 保持这棵树是平衡二叉树。更新也是 O(log(N))。
也可多叉。多个儿子从左到右递增。搜索效率最高，存储不使用二叉树，索引要存在内存、磁盘上。
100 万节点平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。磁盘随机读一个数据块需要 10 ms 左右的寻址时间。 100 万行表，二叉树来存储，单独访问一个行可能需要 20 个 10 ms 时间，可真够慢的。?
查询尽量少地读磁盘，访问尽量少的数据块。“N 叉”树中的“N”取决于数据块的大小。
InnoDB一个整数字段索引为例，N 差不多是 1200。树高4，可存 1200 的 3 次方个值，这已经 17 亿了。树根数据块在内存中，10 亿行表上一个整数字段的索引，最多访问 3 次磁盘。第二层很大概率在内存中，访问磁盘平均次数更少。
N 叉树读写上的性能优点，适配磁盘的访问模式，广泛应用数据库引擎。
实战内容:
MySQL 中，索引是在存储引擎层实现，没有统一索引标准，即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。
InnoDB 的索引模型
根据主键顺序以索引形式存放的，为索引组织表。用 B+ 树索引模型，数据存在 B+ 树中。每个索引对应一棵 B+ 树(InnoDB 里)
主键为 ID 表，字段k 上有索引。建表语句是：
mysql> createtable T(
id int primarykey,
k int not null,
name varchar(16),
index(k))engine=InnoDB;
表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。
文章图片
图 4 InnoDB 的索引组织结构 根据叶子节点的内容，索引类型分为:
(1)主键索引的叶子节点存的是整行数据。聚簇索引（clustered index）。
(2)非主键索引的叶子节点内容是主键的值。二级索引（secondary index）。
查询有什么区别？
select * from T where ID=500，只需搜索 ID 这棵 B+ 树；
select * from T where k=5，先搜k 索引，ID 值500，再到ID 索引树搜索。过程称为回表。
非主键索引查询需多扫描一棵索引树。尽量用主键查询。
索引维护
1、插入ID = 700，R5 后插入。 ID = 400，逻辑上挪动后面数据，空出位置。
如R5 数据页满了， B+ 树算法，申请新数据页，挪动部分数据。称为页分裂。性能受影响。分到两个页中，整体空间利用率降低大约 50%。
相邻两个页删除数据，做合并。
2、例：用身份证号做主键，还是用自增主键呢？
非主键索引的叶子节点上都是主键的值。身份证号做主键，二级索引的叶子节点约 20 个字节，整型做主键，只要 4 个字节。
主键长度越小，普通索引叶子节点越小，占用空间越小。性能更好
3、业务字段做主键场景（KV 场景）：
（1）只有一个索引；
（2）唯一索引。
没有其他索引，不考虑其他索引的叶子节点大小问题。将索引设置为主键，避免搜索两棵树。
小结
InnoDB 用B+ 树结构，配合磁盘的读写特性，减少单次查询磁盘访问次数。
自增主键，占用的空间最小。无绝对
重建索引 k：
alter table Tdrop index k;
alter table T addindex(k);
重建主键索引：
alter table Tdrop primary key;
alter table T addprimary key(id);
是否合理，更好方法是什么？
索引可能因为删除，页分裂，数据页空洞，重建索引，数据顺序插入，利用率最高，更紧凑、省空间。
重建主键不合理。删除/创建主键，表将重建。第一个语句白做了。这两个语句，可用 alter table代替
评论1？
“N叉树”的N值在MySQL中是可以被人工调整的么？曾经面试被问到
1. 首先5.6以后可以通过控制page的大小间接控制；（按照调整key大小的思路来说）
2.计算方法，前缀索引，调整K大小；
【04|04 | 深入浅出索引（上）有问题未解答】
推荐阅读
- Y房东的后半生14
- 陇上秋二|陇上秋二 罗敷媚
- MediaRecorder前后摄像头同时录像
- live|live to inspire 一个普通上班族的流水账0723
- 上班后阅读开始变成一件奢侈的事
- 危险也是机会
- “精神病患者”的角度问题
- 亲子日记第186篇，2018、7、26、星期四、晴
- 海院（实干是海院风景（上））
- 带有Hilt的Android上的依赖注入