数据库作为项目中必不可少且运行速度相对较慢的一环,尤其是在大数据量下保证其更高的性能、更稳定的性能是每个后端程序员必备的技能。MySQL在执行查询语句时,会通过IO扫描磁盘,遍历数据表中的每一条数据,时间复杂度为O(N),当数据量达到百万级别时,查询的速度会极慢,严重影响用户体验。
索引是一种数据结构,是对记录集的一个或多个字段的值进行排序的存储结构。
A database index is a data structure that improves the speed of operations in a table. Indexes can be created using one or more columns, providing the basis for both rapid random lookups and efficient ordering of access to records. 数据库索引是一种提高表操作速度的数据结构。 可以使用一列或多列创建索引,为快速随机查找和有效排序记录访问提供基础。
创建数据表时添加索引
CREATE UNIQUE INDEX index_name ON table_name ( column1, column2,...);
以修改数据表的形式添加索引
ALTER TABLE testalter_tbl ADD INDEX (c);
未加索引时查询某表:
explain
select * from employee where name = '陈静';
使用DDL语句给数据表Name字段增加索引:
alter table employee add index name_index (name);
再次执行查询语句,使用explain查看结果
MySQL在命中索引后,查询时不再扫描全表,而是通过索引找到对应数据。
索引的出现其实是为了提高数据查询的效率,就像书的目录一样,根据目录可以快速定位到内容,类比于索引,根据索引提供指向存储在表的指定列中的数据值的指针,根据指针找到包含该值的行。
举一个形象点的例子:将一张数据表比喻成一个字典,数据表的每一条数据都相当于字典中的每一个字,当我们需要查询某个字时,需要从字典的第一页开始翻,直到找到我们要查找的目标字,机器擅长重复性劳动,不会觉得“累”,但是字典里的字实在是太多了,即使机器不怕“累”,但时效终究是我们追求的东西,因此,我们需要一个方法快速找到目标字,我们根据字的拼音首字母分类,将相同字母的字放在一起,即某个字母看做一个节点,该节点下都是同类的汉字,这样在查询时便缩小了查询范围,所有的分类放在一起就是目录,它记录了目标字(数据)所在的具体页数(行数)。
常见的索引数据结构分为以下几种:
哈希表将待查询的值放入key中,value值放入数组中,在查询时通过计算Key的哈希值找到对应的值,因此哈希表适用于等值查询的场景(如:where id =1;
),但哈希表并不是有序的,因此在区间查询(如where id between 1 and 5
),在区间查询时,效率比较低。
有序数组在等值查询和范围查询场景中的性能都非常优秀。
仅看查询效率,有序数组是最好的数据结构,使用二分法查询可以快速查询到目标值,时间复杂度是O(log(N))
。但是在中间插入一个记录时就必须得挪动后面所有的记录,成本太高。
二叉树的特点是:父节点左子树所有节点的值小于父节点的值,右子树所有节点的值大于父节点的值。查询复杂度是O(log(N))
。
二叉树是搜索效率最高的,但是实际上没有多少数据库存储使用,因为索引不止存在于内存中,还要写在磁盘上。数据量较大时,二叉树的树过高,查询时需要访问过多节点,即需要硬盘多次寻址,这是一个耗时操作。
N叉树 概念:允许树的每个节点可以有两个以上的子节点,那么这个树就称为N阶多叉树。
MySQL默认一个节点的长度为16K,一个整数(bigint)字段索引的长度为8B,另外每个索引还跟着6B的指向其子树的指针;所以16K/14B≈1170。
树高是4的时候,就可以存1200的3次方个值(17亿),树根的数据总是存在内存中的,一个10亿行的表上一个整数字段的索引,查找一个值最多只需要访问3次磁盘。树的第二层也大概率在内存中,那么访问磁盘的次数就少了。
N 叉树由于在读写上的性能优点,以及适配磁盘的访问模式,已经被广泛应用在数据库引擎中。
在开发中我们会遇到给生产数据库的表增加索引的情况,该行为属于是DDL操作,在执行时数据表会进行锁表,即表在锁定期间不可对表进行操作,必须等锁被释放才可以进行操作,给表增加索引会会触发为现有数据重建索引,可能会导致数据库长时间阻塞,事务不能被提交,最终会拖垮数据库,因此在给线上数据表增加索引时,可以使用如下操作:
按新结构创建新表 -> 将旧表数据迁移至新表 -> 重命名两个表(三步都通过编写sql语句完成,比手动操作快,第二步的数据迁移操作视情况而定)。