索引:为了提高数据查询的效率,就像书的目录一样。
索引的常见模型
哈希表
[img=40%,40%]https://static001.geekbang.org/resource/image/0c/57/0c62b601afda86fe5d0fe57346ace957.png?wh=1142*856[/img] 图中,User2 和 User4 根据身份证号算出来的值都是 N,后面还跟了一个链表。假设,这时候你要查 ID_card_n2 对应的名字是什么,处理步骤就是:首先,将 ID_card_n2 通过哈希函数算出 N;然后,按顺序遍历,找到 User2。
需要注意的是,图中四个 ID_card_n 的值并不是递增的,好处是增加新的 User 时速度会很快,只需要往后追加。缺点是,因为不是有序的,所以哈希索引做区间查询的速度是很慢的。****
哈希表结构适用于只有等值查询的场景。
有序数组
有序数组在等值查询和范围查询场景中的性能就都非常优秀。
[img=40%,40%]https://static001.geekbang.org/resource/image/bf/49/bfc907a92f99cadf5493cf0afac9ca49.png?wh=1142*787[/img] 要查 ID_card_n2 对应的名字,用二分法就可以快速得到,时间复杂度是 O(log(N))。同时很显然,这个索引结构也支持范围查询。
仅仅看查询效率,有序数组就是最好的数据结构。但是,在需要更新数据的时候就麻烦了,往中间插入一个记录就必须得挪动后面所有的记录,成本太高。
所以,有序数组索引只适用于静态存储引擎。
N 叉树
二叉搜索树的特点是:父节点左子树所有结点的值小于父节点的值,右子树所有结点的值大于父节点的值。
[img=40%,40%]https://static001.geekbang.org/resource/image/04/68/04fb9d24065635a6a637c25ba9ddde68.png?wh=1142*856[/img] 如果你要查 ID_card_n2 的话,图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。时间复杂度是 O(log(N))。
为了维持 O(log(N)) 的查询复杂度,需要保持这棵树是平衡二叉树。为了做这个保证,更新的时间复杂度也是 O(log(N))。
二叉树是搜索效率最高的,但是实际上大多数的数据库存储却并不使用二叉树。其原因是,索引不止存在内存中,还要写到磁盘上。
InnoDB 的索引模型
在 MySQL 中,索引是在存储引擎层实现的。
InnoDB 使用了 B+ 树索引模型,每一个索引在 InnoDB 里面对应一棵 B+ 树。
一个主键列为 ID 的表,表中有字段 k,并且在 k 上有索引。
表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6),两棵树的示例示意图如下。
[img=40%,40%]https://static001.geekbang.org/resource/image/dc/8d/dcda101051f28502bd5c4402b292e38d.png?wh=1142*856[/img] InnoDB 的索引组织结构根据叶子节点的内容,索引类型分为主键索引和非主键索引。
- 主键索引的叶子节点存的是整行数据。在 InnoDB 里,主键索引也被称为聚簇索引(clustered index)。
- 非主键索引的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。
基于主键索引和普通索引的查询区别?:
- select * from T where ID=500,即主键查询方式,则只需要搜索 ID 这棵 B+ 树;
- select * from T where k=5,即普通索引查询方式,需要先搜索 k 索引树,得到 ID 值为 500,再到 ID 索引树搜索一次。这个过程称为回表。
基于非主键索引的查询需要多扫描一棵索引树,因此在应用中应该尽量使用主键查询。
索引维护
- 主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。
- 有业务逻辑的字段做主键,则往往不容易保证有序插入,写数据成本相对较高。
从性能和存储空间方面考量,自增主键往往是更合理的选择。
同时适合用业务字段直接做主键的场景是:
由于没有其他索引,所以也就不用考虑其他索引的叶子节点大小的问题。
这时候优先考虑“尽量使用主键查询”原则,直接将这个索引设置为主键,可以避免每次查询需要搜索两棵树。
问:对于 InnoDB 表 T,如果你要重建索引 k,你的两个 SQL 语句可以这么写:- alter table T drop index k;
- alter table T add index(k);
复制代码 如果你要重建主键索引,也可以这么写:- alter table T drop primary key;
- alter table T add primary key(id);
复制代码 对于上面这两个重建索引的作法,说出你的理解。
答:为什么要重建索引。索引可能因为删除,或者页分裂等原因,导致数据页有空洞,重建索引的过程会创建一个新的索引,把数据按顺序插入,重建索引使得页面的利用率最高,也就是索引更紧凑、更省空间。
重建索引 k 的做法是合理的,可以达到省空间的目的。但是,重建主键的过程不合理。
不论是删除主键还是创建主键,都会将整个表重建。所以连着执行这两个语句的话,第一个语句就白做了。这两个语句,你可以用这个语句代替 : alter table T engine=InnoDB。
来源:https://www.cnblogs.com/itiancong/p/18023061
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作! |