常见的数据结构中, 哈希表和二叉平衡树的查找效率分别是O(1)和O(logn), 是效率最快的两个, MySQL也毫不意外的使用了这两种数据结构来做索引。 MySQL索引的数据结构有两种选择, B+Tree 和 Hash。
MySQL不仅要保存数据,还要保存一下索引文件每次更新添加了索引列的字段,都会调整因为更新所带来的减值变化后的索引信息。
索引也是一张表,该表保存了主键与索引字段,并指向实体表的记录,所以索引列也是要占用空间的。
create index 索引名 on 表名 (字段名);
5.7版本InnoDB存储引擎,单表最大1017列,最多包含64个索引,联合索引最多16列。
https://dev.mysql.com/doc/refman/5.7/en/innodb-limits.html
CREATE TABLE `test_index` (
`c` bigint(16) NOT NULL AUTO_INCREMENT,
`c1` varchar(16) DEFAULT NULL,
`c2` varchar(16) DEFAULT NULL,
`c3` varchar(16) DEFAULT NULL,
`c4` varchar(16) DEFAULT NULL,
`c5` varchar(16) DEFAULT NULL,
`c6` varchar(16) DEFAULT NULL,
`c7` varchar(16) DEFAULT NULL,
`c8` varchar(16) DEFAULT NULL,
`c9` varchar(16) DEFAULT NULL,
`c10` varchar(16) DEFAULT NULL,
`c11` varchar(16) DEFAULT NULL,
`c12` varchar(16) DEFAULT NULL,
`c13` varchar(16) DEFAULT NULL,
`c14` varchar(16) DEFAULT NULL,
`c15` varchar(16) DEFAULT NULL,
`c16` varchar(16) DEFAULT NULL,
`c17` varchar(16) DEFAULT NULL,
PRIMARY KEY (`c`), KEY `idx_18` (`c1`,`c2`,`c3`,`c4`,`c5`,
`c6`,`c7`,`c8`,`c9`,`c10`,`c11`,`c12`,`c13`,`c14`,`c15`,`c16`)
) ;
create unique index 索引名 on 表名 (字段名)
用户表,用户手机号码注册注册,手机号码创建唯一索引,重复手机号码新增,提示索引冲突。
单个组合索引,mysql的5.7版本innodb引擎,允许最大设置16个列。
create table 表名(
字段名1 int(11) not null,
字段名2 varchar(10) not null, index(字段名1,字段名2)
);
在多个字段上创建的索引,只有在查询条件中使用了创建索引时的第一个字段,索引才会被使用。
EXPLAIN SELECT * FROM test_index WHERE c2='123';
添加索引也不会显著的增加查询速度,减少用户响应时间。 因为需要占用空间,反而会降低数据库的整体性能。
索引已经排序,其保存的时候指定的范围是连续的,查询可以利用索引的排序,提高查询效率。 示例:年龄14到18的学生。
排序和统计的字段如果通过索引去访问,将大大提高排序速度。
只要列中包含有NULL值都将不会被包含在索引中,复合索引中只要有一列含有NULL值,那么这一列对于此复合索引就是无效的。 建议:数据库设计时不要让字段的默认值为NULL。
CREATE TABLE `user_info` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(255) DEFAULT NULL,
`nick` varchar(255) DEFAULT NULL,
`sex` tinyint(2) DEFAULT NULL,
`score` int(3) DEFAULT NULL,
KEY `idx_id` (`id`),
KEY `idx_score` (`score`) USING BTREE
);
insert into user_info values (1, '杨过', 'yangguo', '1', 90);
insert into user_info values (2, '小龙女', 'xiaolongnv', '0', 88);
insert into user_info values (3, '黄药师', 'huangyaoshi', '1', 75);
insert into user_info values (4, '郭襄', 'guoxiang', '0', 66);
insert into user_info values (5, '何足道', 'hezudao', '1', 50);
insert into user_info values (6, '独孤求败', 'duguqiubai', '1', 55);
insert into user_info values (7, '方东白', 'fangdongbai', '1', 88);
insert into user_info values (8, '赵敏', 'zhaomin', '0', 75);
insert into user_info values (9, '程灵素', 'chenglingsu','0', 66);
-- 使用了索引
EXPLAIN SELECT * FROM user_info WHERE score = 55;
-- 未使用索引
EXPLAIN SELECT * FROM user_info WHERE score != 55;
字符串未使用引号
-- 使用了索引
EXPLAIN SELECT * FROM user_info WHERE sex = '0';
-- 未使用索引
EXPLAIN SELECT * FROM user_info WHERE sex = 0;
EXPLAIN SELECT * FROM user_info WHERE score LIKE '5%';
-- 使用了索引
EXPLAIN SELECT * FROM user_info WHERE score = 55;
-- 未使用索引
EXPLAIN SELECT * FROM user_info WHERE score = 55 OR nick='yangguo';
相减,身份证截取,日期格式化,字符串拼接比较等。
-- 未使用索引
EXPLAIN SELECT * FROM user_info WHERE substr(name, 2, 2) = '灵素';
-- 使用了索引
EXPLAIN SELECT * FROM user_info WHERE name = '程灵素';
-- 使用了索引
EXPLAIN SELECT * FROM user_info WHERE score = 75;
-- 未使用索引
EXPLAIN SELECT * FROM user_info WHERE score-1 = 74;
-- 使用索引
EXPLAIN SELECT * FROM user_info WHERE score IS NULL;
-- 不使用索引
EXPLAIN SELECT * FROM user_info WHERE score IS NOT NULL;
若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
左、右子树也分别为二叉树
链表的查找时间复杂度是O(N),这时候最多需要7次才能查到所需数据。
二叉搜索树查找数据的时间复杂度是O(logN),如图所示,最多查找3次就可以查到所需数据。
极端情况下,二叉查找树可能退化成线性链表 非平衡树,不适合做数据库索引。
代码实现:
https://gitee.com/ischenshuai/demo/tree/master/dataStruct/
tree/binary-tree-demo
B树是有序数组+平衡多叉树,总体有序。 树的高度越高,查找次数越多,也就是磁盘IO次数越多,耗时越长。 降低树的高度,把二叉树变成N叉树,即B树。
高度更低,每个节点含有多个元素,查找的时候一次可以把一个节点中的所有元素加载到内存中作比较,两种改进都大大减少了磁盘IO次数。
节点必须是红色或者黑色
根节点必须是黑色
叶子节点全部为黑色,叶子是NIL结点
每个红色结点的两个子结点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色结点)
从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
限制了左右子树的树高,不会相差过大。查询效率高
规则复杂,可能红黑树转化,开销大
有序数组链表+平衡多叉树
将车库中的车牌号按简称排列,重复的简称,可成为hash冲突。 多个不同的值通过算出了同一个hash值被称之为hash冲突。
等值比较,使用hash索引效率更高。 由于是一次定位数据,不像BTree索引需要从根节点到枝节点,最后才能访问到页节点这样多次IO访问,所以检索效率远高于BTree索引。
Hash 索引指向的数据是无序的,而 B+ 树的叶子节点是个有序的链表。
对于联合索引来说,Hash 索引在计算 Hash 值的时候是将索引键合并后再一起计算 Hash 值,所以不会针对每个索引单独计算 Hash 值。因此如果用到联合索引的一个或者几个索引时,联合索引无法被利用。
Hash 索引指向的数据是无序的,因此无法起到排序优化的作用,而 B+ 树索引数据是有序的,可以起到对该字段 ORDER BY 排序优化的作用。
B+ 树使用 LIKE 进行模糊查询的时候,LIKE 后模糊查询的话就可以起到优化作用。
对于等值查询来说,通常 Hash 索引的效率更高,但是,索引列的重复值如果很多,效率就会降低。这是因为遇到 Hash 冲突时,需要遍历桶中的行指针来进行比较,找到查询的关键字,非常耗时。所以,Hash 索引通常不会用到重复值多的列上,比如列为性别、年龄的情况等。
在 update 语句的 where 条件没有使用索引,就会全表扫描。 使用索引后,使用“行锁”进行udpate,只锁当前行。不影响其他行的查询更新