张亚飞 发表于 2023-6-3 21:26:33

04_深入浅出索引(上)

04_深入浅出索引(上)


索引的概念

索引的概念:索引是一种数据结构,用于提高数据库查询效率。就像一本书的目录一样,索引可以帮助数据库在大量数据中快速找到需要的数据,减少查询时间和资源消耗。
除了提高查询效率,索引还可以帮助数据库实现唯一性约束、主键约束和外键约束等数据完整性约束。
例如,在一个用户表中,我们可以使用用户ID作为主键,并在ID列上创建一个唯一索引,以保证每个用户ID都是唯一的。

常见索引模型

常见索引模型:索引模型是指索引的数据结构和组织方式。常见的索引模型有哈希表、有序数组和搜索树等。
哈希表:哈希表是一种将键映射到值的数据结构,它通过哈希函数将键转换为数组的下标,然后将值存储在该下标处。
哈希表适用于等值查询场景,例如在一个存储用户信息的表中,我们可以使用用户ID作为哈希表的键,来快速查找某个用户的信息。
有序数组:有序数组是一种按照元素大小顺序排列的数组,它适用于等值查询和范围查询场景。
例如,在一个按照身份证号排序的用户表中,我们可以使用二分法快速查找某个身份证号对应的用户信息。但是,有序数组的更新成本较高,适用于静态存储引擎。
搜索树:搜索树是一种按照元素大小顺序组织的树形结构,它适用于等值查询和范围查询场景。
例如,在一个按照用户ID排序的用户表中,我们可以使用二叉搜索树快速查找某个用户ID对应的用户信息。但是,搜索树的查询效率高,但写入和更新成本高,不适用于大规模数据存储。
扩充例子:在一个电商网站的订单表中,我们可以使用订单ID作为哈希表的键,来快速查找某个订单的信息。在一个按照订单时间排序的订单表中,我们可以使用二分法快速查找某个时间段内的订单信息。在一个按照商品价格排序的商品表中,我们可以使用B树来快速查找某个价格区间内的商品信息。
二叉树虽然是搜索效率最高的,但是实际上大多数的数据库存储却并不使用二叉树,因为索引不仅存在内存中,还要写入磁盘。
为了让查询尽量少地读磁盘,我们需要让查询过程访问尽量少的数据块。因此,我们应该使用“N叉”树来代替二叉树。在“N叉”树中,“N”的大小取决于数据块的大小。
以InnoDB的一个整数字段索引为例,这个“N”大约是1200。当这棵树高为4时,就可以存储1200的3次方个值,这已经达到了17亿。考虑到树根的数据块总是在内存中,一个10亿行的表上一个整数字段的索引,查找一个值最多只需要访问3次磁盘。实际上,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。
扩充阐述:在实际的数据库应用中,磁盘I/O是非常耗时的操作。因此,我们需要尽量减少磁盘I/O的次数,以提高数据库的查询效率。为了实现这个目标,数据库存储引擎通常会采用B树、B+树、R树等数据结构来实现索引。这些数据结构都是基于“N叉”树的结构,能够有效地减少磁盘I/O的次数,提高查询效率。
例如,在一个电商网站的商品表中,我们可以使用商品价格作为B+树的键,来快速查找某个价格区间内的商品信息。B+树在叶子节点上保存了所有数据记录的指针,而非像B树那样在每个节点上都保存数据记录,因此能够减少磁盘I/O的次数,提高查询效率。
总结:为了提高数据库的查询效率,我们需要选择合适的索引模型,并采用相应的数据结构来实现索引。在选择数据结构时,需要考虑具体的查询场景和存储引擎特点。常见的索引模型有哈希表、有序数组和搜索树等,而常用的数据结构有B树、B+树、R树等。通过选择合适的索引模型和数据结构,可以有效地提高数据库的查询效率,降低磁盘I/O的次数,从而提升数据库的整体性能。

数据库底层存储的核心就是基于这些数据模型的。每碰到一个新数据库,我们需要先关注它的数据模型,这样才能从理论上分析出这个数据库的适用场景。

B 树和 B+ 树

B树和B+树都是多路搜索树,是一种常用的数据结构,在数据库、文件系统等领域广泛应用。它们不是二叉树,而是多叉树。
B树和B+树的主要区别在于它们的索引结构和叶子节点的存储方式不同。B树的每个节点都包含键值和指向子节点的指针,而B+树的非叶子节点只包含键值和指向子节点的指针,而所有的数据都存储在叶子节点中。
B树的搜索过程比较复杂,因为需要在非叶子节点和叶子节点之间不断切换,而B+树的搜索过程更加简单,因为只需要在叶子节点中进行搜索。此外,B+树的叶子节点是通过链表相连的,可以方便地进行范围查询和遍历。
因此,B+树通常比B树更适合在数据库中使用,因为它能够更快地进行范围查询和遍历。但是,在某些场景下,B树也可能比B+树更适合使用,例如需要快速插入和删除数据的场景。

InnoDB 的索引模型

在InnoDB中,表都是根据主键顺序以索引的形式存放的,这种存储方式的表称为索引组织表。
InnoDB 使用的是 B+ 树索引模型,所以数据都是存储在 B+ 树中的,每一个索引在 InnoDB 里面对应一棵 B+ 树。
索引类型分为主键索引和非主键索引。

[*]主键索引的叶子节点存的是整行数据。在 InnoDB 里,主键索引也被称为聚簇索引(clustered index)。
[*]非主键索引的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。
举个例子来说,假设我们有一个学生表,其中主键为学生ID。如果我们要查询学号为1001的学生的所有信息,如果使用主键索引,则只需要搜索ID这棵B+树,而如果使用非主键索引,则需要先搜索学号这棵B+树得到ID的值为1001,再到ID索引树搜索一次,这个过程称为回表。
因此,使用主键索引查询可以减少一次搜索,提高查询效率。
在应用中我们应该尽量使用主键查询,以减少查询时间和提高性能。
但是,在实际使用中,我们也需要根据具体情况来选择使用哪种索引类型。例如,如果我们需要查询学生的所有信息,而不仅仅是学号,那么使用主键索引就无法满足我们的需求,这时候就需要使用非主键索引。
InnoDB的索引模型是数据库中非常重要的一个概念,不同的索引类型在查询效率和使用场景上都有着不同的优缺点。我们需要根据具体需求来选择使用哪种索引类型,以提高数据库的性能和效率。

索引维护

索引维护是数据库中非常重要的一部分,它确保了数据的快速查询和排序。
在B+树中,为了维护索引有序性,在插入新值的时候需要做必要的维护。
这个过程中,当插入的数据页已经满了,就需要进行页分裂操作。这个过程会申请一个新的数据页,并将部分数据挪动过去,影响了性能和数据页的利用率。
不过,有分裂就有合并。当相邻两个页由于删除了数据,利用率很低之后,会将数据页做合并,这个过程可以认为是分裂过程的逆过程。
另外,对于自增主键的使用场景,我们需要分析哪些场景下应该使用自增主键,而哪些场景下不应该。
自增主键的插入数据模式,是递增插入的场景,每次插入一条新记录,都是追加操作,都不涉及到挪动其他记录,也不会触发叶子节点的分裂。
而有业务逻辑的字段做主键,则往往不容易保证有序插入,这样写数据成本相对较高。
此外,从存储空间的角度来看,如果用身份证号等字符串类型的字段做主键,那么每个非主键索引的叶子节点上都是主键的值,占用的空间较大。因此,自增主键往往是更合理的选择。
但是,对于只有一个索引且必须是唯一索引的场景,可以直接将这个索引设置为业务字段做主键,避免每次查询需要搜索两棵树。
假设你在设计一个订单系统,其中包含订单的ID、用户ID、商品ID、数量、价格等信息。如果你需要在该系统中快速查找某个订单的信息,可以在订单ID字段上建立一个唯一索引,这样就可以快速查找到该订单的信息。但是,如果你需要根据用户ID或商品ID等信息进行查询,那么就需要在这些字段上建立索引,以保证查询的速度和效率。
在这种情况下,如果使用自增主键作为主键,可以保证数据的有序插入和查询,提高了查询效率。每次插入一条新记录,都是追加操作,都不涉及到挪动其他记录,也不会触发叶子节点的分裂。此外,自增主键的数据类型通常为整型,占用的存储空间相对较小,可以节省存储空间。
但是,如果你的业务场景需要根据用户ID或商品ID等字段进行频繁的查询和排序,那么就应该考虑将这些字段作为主键。在这种情况下,使用自增主键可能会导致数据的插入顺序与查询顺序不一致,降低查询效率。
因此,在设计主键时,需要根据具体业务场景进行选择。


来源:https://www.cnblogs.com/LuoQi11/p/04_early-simple-index-top-27akdi.html
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作!
页: [1]
查看完整版本: 04_深入浅出索引(上)