索引
1.什么是数据库索引?
1.1 概念
- 索引是一种特殊的文件,包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引,并指定索引的类型,各类索引有各自的数据结构实现。
索引(index)可以说是一本书的目录(index)。【两者的英文是同一个只是表现的形式不一样。】
1.2 作用
- 数据库中的表、数据、索引之间的关系,类似于书架上的图书、书籍内容和书籍目录的关系。
- 索引所起的作用类似书籍目录,可用于快速定位、检索数据。
- 如果没有索引,在数据库中进行查找就要把整个表遍历一遍,很耗时.
- 索引对于提高数据库的性能 (主要是提高查找效率,修改增加删除效率还会有所下降) 有很大的帮助。
- 本质上索引就是为了避免数据库进行顺序查找,提高查找效率.
1.3 使用场景
要考虑对数据库表的某列或某几列创建索引,需要考虑以下几点:
- 数据量较大,且经常对这些列进行条件查询。
- 该数据库表的插入操作,及对这些列的修改操作频率较低。
- 索引会占用额外的磁盘空间。(用空间效率换取时间效率) 满足以上条件时,考虑对表中的这些字段创建索引,以提高查询效率。 反之,如果非条件查询列,或经常做插入、修改操作,或磁盘空间不足时,不考虑创建索引。
1.4 索引的优缺点
思考一个问题:
树的目录一旦决定了,后续每次对书的内容进行调整时,都可能会印象到目录的准确性,就需要重新调整目录。 数据库的索引也是一样的情况:
当我们 对 数据进行“增删改”操作的时候,往往也需要同步调整索引的结构。
索引带来的好处:提高了查询效率
索引带来的坏处:占用了更多的空间,拖慢了增删查改的速度。
从表面来上看,似乎索引的坏处 比 索引带来的好处要多。但!这不必意味着 弊大于利!! 因为在实际需求的场景中,查询操作往往是最高频率的操作。 相对于“增删改” 的使用频率则低的可怜。 因此,查询作为一个高频操作,索引对其来说是不可缺少, 另外,
有索引之后对于查询的效率的提升使非常巨大
!!! 当MySQL里面的数据量级 达到千万级别的时候(一个表里就有几千万,甚至破亿的数据)再去遍历表,就会非常非常的低效!!! 在另一方面:MySQL在进行数据比较的时候,不是像我们编程那样,一个for循环(这样的想法是错误的)
编程上的查询是在内存中的比较;MySQL中的比较是在硬盘上比较。
也就是说:在MySQL中的每一次比较都会涉及到硬盘的 IO 操作。
又因为硬盘的 IO 的 访问速度 比 内存 慢 3 ~ 4 个数量级(几千~万倍)。 所以,如果是查询的操作更是慢上加慢!!!
【这里又一次体现了索引的好处:能使这里的查找效率提高数倍】
1.5 如何使用
- 创建主键约束(PRIMARY KEY)、唯一约束(UNIQUE)、外键约束(FOREIGN KEY)时,会自动创建对应列的索引。
查看索引
命令格式:show index from 表名;
show index from student;
其作用:查看一个数据表上都有哪些索引
创建索引
命令格式:
create index 索引名字 on 表名(列名)
注意:
创建索引这件事是一个非常低效
的事情,尤其是当前表里面已经有很多数据
的时候。 它需要给该列的每一行数据都设置一个索引,因此在数据量庞大的情况下,创建的索引的过程是非常耗时的!因此,以后在工作的时候,看到某个数据库的一个表没有索引,
千万不要贸然去创建一个索引
你啪的回车一敲,下一秒数据库就挂了。操作数据库本身就是一个危险操作。必须时刻小心谨慎。
删除某个表中的索引
命令格式:
drop index 索引名字 on 表名
删除索引操作和创建同理,都是非常低效的事情,也容易让数据库挂了
2.索引的数据结构是什么?
2.1 可以是二叉搜索树或者红黑树吗?
不可以
二叉搜索树
的平均查找效率是O(logN)
- 如果数据很多的话,二叉搜索树最多俩个分支,所以
树的深度会很大,查找效率其实不高
- 如果是查找范围的时候还需要对二叉搜索树进行中序遍历 (因为二叉搜索树中序遍历是有序序列) 又不是很高效
O(N)
2.2 可以是哈希表吗?
不可以
- 如果是处理相等情况,哈希表很高效
- 但是
哈希表不可以处理其他逻辑,比如范围查找
> >= < <= between and - 因为哈希的查找是把key带入哈希函数得到下标,再根据下标取对应的链表,再去遍历链表比较key是否相等,无法进行范围查找
2.3 可以是B树吗?
- 本质可以,但为了更高的效率不选它
B树与二叉树差异:
- 为了结点不是2叉而是
N叉
- 为了结点不是存储一个数据,而是可能存储多个数据
每个节点存储数据的个数和该节点的度是有关系的 度=存储数据的个数+1
- 此时在B树上查找就是一个N分查找,效率比二叉树还高
- 由于每个及节点存储了多个数据,每个节点又有多个度,所以和二叉树相比,B树的高度会低很多,查找起来效率一会高一下.而且简单的范围查找会容易一些.
在整个数据量的条件一定的情况下,N叉搜索树的高度 一定比 二叉搜索树要低。 在数据库中使用的这个多叉树,又不太一样,是一个很特殊的树,我们称为 B+ 树。 【B+ 树 是 数据库中最常见的数据结构】 注意!数据库有很多种,每个数据库底层又支持多种存储引擎 这些存储引擎实现了数据库具体按照什么结构来存储的程序。 那么就意味着 每个存储引擎 存储数据的结构 可能都不一样,背后的索引数据结构可能也不同。 所以,这里面可能会有很多种多叉树来去表示这里的数据结构。 只是 B+ 树 是 最常用的一种数据结构。 那么,B+ 树 又是什么样子的? 想要 理解 B+ 树,需要先理解它的前身 B 树( B-树:这个是B树的另一种写法,而不是B减树)
2.4 可以是B+树吗?
与B-树相比的差异:
每一层的元素之间都链接在一起
数据(表的一行记录)只存在叶子节点上,非叶子节点只保存一些辅助查找的边界信息
- 查询任一条记录都比较平均,不会出现效率差异很大的情况
- 不需要额外进行中序遍历,遍历叶子节点就是中序结果,所以处理范围查找很高效
- 叶子放在磁盘上,非叶子放在内存中,减少了访问磁盘的次数,查找也就更高效了,而且索引在内存中实际开销有不高
- 索引引起的效果就是加快查找效率, 减慢插入删除修改的效率 (因为需要同步调整索引结果)
- 索引也会占用额外空间(本质上使用空间换取时间)
- 给具体表中某列加索引的时候,加在主键的索引和加在其他列的索引是截然不同的.
- 主键索引的叶子结点value存的是表的一行完整数据, 其他索引的叶子节点value只存的是主键的信息(如id)
因为B树 是 B+树的前身,那么B+树想对比B树又做出了那些改变?
疑问:为什么B+树这么去构建?
你可以这么认为 B+ 树 就是为了 数据库索引量身打造的!!!!
- 使用B+树进行查找的时候,整体IO次数也是比较少的。
所有的查询最终多会落在叶子结点上
,每次查询的 IO 次数都是差不多的,故查询的速度是稳定的,相差不大。叶子结点用链表链接
之后,非常适合进行范围查找所有的数据存储(数据又称载荷)都是放到叶子结点上的。也就是说非叶子结点中只需要保存key值就可以了
。因此非叶子节点整体占用空间较小,甚至可以加载到内存中。(一旦能够全部放在内存里,此时硬盘上的IO次数几乎就为零了)
例如:
找到 大于等于5,且小于等于 11 的值。
所有的数据存储(数据又称载荷)都是放到叶子结点上的。也就是说非叶子结点中只需要保存key值就可以了。因此非叶子节点整体占用空间较小,甚至可以加载到内存中。(一旦能够全部放在内存里,此时硬盘上的IO次数几乎就为零了)