04 | 讲深入浅出索引（上）

04 | 讲深入浅出索引（上）
索引结构 : 哈希表 , 有序数组 , 查找树 (都是查找表)
哈希只能 equal , 数组和树都能euqal , range , 并且是有序的 , 所以可以二分
树的更新成本较数组低
二叉树是查找效率最高的 , 但是索引要存在磁盘里 , 所以都是用多叉树
100w节点的平衡二叉树 log100w=20 , 树高20 , 查询要访问20个数据块
磁盘随机读数据库需要10ms寻址时间
二叉树访问一行=20*10ms=200ms
N叉树减少树高度
innodb的int类型索引 , N为1200 , 若树高为4 1200^3=17亿 , 只需要访问3次磁盘 , 因为根节点在内存中 , 第二层也可能已经在内存中 , 则更少
其他类似的优化数据结构 : 跳跃表,LSM树?
主键索引叶子节点存的整行数据 , 也叫聚簇索引
非主键索引存的是主键ID , 成为二级索引
非主键索引需要多扫描一颗树 , 成为回表
如果插入在ROW5所在的数据页(<=ROW5),但是R5的数据页已经满了 , 此时需要申请新的数据页,挪一部分过去 , 成为页分裂
页分裂影响性能 , 还影响空间利用率
自增主键不会在中间插入,不挪动数据 , 因此没有页分裂
如果用身份证当主键(20)字节, 普通索引叶子节点需要存的空间就会变大 , int 4字节 , bigint 8字节
自增主键通常是更合理的选择
只有一个索引的表则可以用类似身份证当主键 类似K,V的场景
重建索引的目的是消除页分裂导致的性能和空间利用效率
重建主键索引不应该用
alter table T drop primary key;
alter table T add primary key(id);
两次操作都会重建整个表, 要用alter table T engine=InnoDB

评论 留言可以当做测试用例 看提问自己能不能解答