从下列几种情况下查找某一个汉字:
-
一堆汉字
-
有拼音目录的字典
-
有部首目录的字典
解决的方案:
- 一个一个找,直接找到为止
- 按照拼音表的顺序找,拼音表是有序的,字在字典中也是有序的,很容易找。
- 根据部首目录来找,先找部首,再找汉字。汉字在字典中是无序的。
加一个汉字,会怎么样,大家可以先想想看。
其实这各结构和数据搜索是很类似的:
- 全表扫描直到找到为止
- 用聚集索引查找
- 用非聚集索引查找
在数据库中,索引的含义与日常意义上的“索引”一词并无多大区别(想想小时候查字典),它是用于提高数据库表数据访问速度的数据库对象。
A
)索引可以避免全表扫描。多数查询可以仅扫描少量索引页及数据页,而不是遍历所有数据页。
B
)
对于非聚集索引,有些查询甚至可以不访问数据页。
C
)
聚集索引可以避免数据插入操作集中于表的最后一个数据页。
D
)
一些情况下,索引还可用于避免排序操作。
当然,众所周知,虽然索引可以提高查询速度,但是它们也会导致数据库系统更新数据的性能下降,因为大部分数据更新需要同时更新索引
表数据按照索引的顺序来存储的。自然界的事物都是按照某一种顺序排列的,当然它只能有一种顺序。所以数据表中的聚集索引只能建立一次。对于聚集索引,叶子结点即存储了真实的数据行,不再有另外单独的数据页。下面会具体介绍。
表数据存储顺序与索引顺序无关。对于非聚集索引,叶结点包含索引字段值及指向数据页数据行的逻辑指针,该层紧邻数据页,其行数量与数据表行数据量一致。
先来看一下索引存储的一个简单的结构,一条索引记录中包含的基本信息包括:键值(即你定义索引时指定的所有字段的值)+逻辑指针(指向数据页或者另一索引页);
当你为一张空表创建索引时,数据库系统将为你分配一个索引页,该索引页在你插入数据前一直是空的。此页此时既是根结点,也是叶结点。每当你往表中插入一行数据,数据库系统即向此根结点中插入一行索引记录。当根结点满时,数据库系统大抵按以下步骤进行分裂:
A
)创建两个儿子结点
B
)将原根结点中的数据近似地拆成两半,分别写入新的两个儿子结点
C
)根结点中加上指向两个儿子结点的指针
通常状况下,由于索引记录仅包含索引字段值(以及
4-9
字节的指针),索引实体比真实的数据行要小许多,索引页相较数据页来说要密集许多。一个索引页可以存储数量更多的索引记录,这意味着在索引中查找时在
I/O
上占很大的优势,理解这一点有助于从本质上了解使用索引的优势。
索引的查找,类似Btree的方式
但Btree有几个问题:
- 左右树的树高不一样,如果查询的索引大部份都在树高的一边,那查询的效率就会偏低了
- 在非叶子节点也可以命中,当索引更新时,会产生极大的消耗。
由于以下的问题,不同的数据对索引存储实现不完全使用Btree,而是经过一个改变。
我们常见的数据库系统,其索引使用的数据结构多是B-Tree或者B+Tree。
MySql, Berkerly DB使用的是B+Tree
Oracle及Sysbase使用的是B-Tree。
B+tree的结构:
B+tree比Btree在性能方面有了很大的提升。
- B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有可能重复出现,以维持B+树的平衡。
- 因为B树键位置不定,且在整个树结构中只出现一次,虽然可以节省存储空间,但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
- B树的查询效率与键在树中的位置有关,最大时间复杂度与B+树相同(在叶结点的时候),最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。
在聚集索引中,叶结点也即数据结点,所有数据行的存储顺序与索引的存储顺序一致。
1
)聚集索引与查询操作
如上图,我们在名字字段上建立聚集索引,当需要在根据
此字段
查找特定的记录时,数据库系统会根据
特定的系统表
查找的此索引的根,然后根据指针查找下一个,直到找到。例如我们要查询“
Green
”,由于
它介于[Bennet,
Karsen]
,据此我们找到了索引页
1007
,在该页中
“Green”
介于
[Greane
,
Hunter]
间
,据此我们找到叶结点
1133
(也即数据结点),并最终在此页中找以了目标数据行。
此次查询的
IO
包括
3
个索引页的查询(其中最后一次实际上是在数据页中查询)。这里的查找可能是从磁盘读取
(Physical Read)
或是从缓存中读取
(Logical Read)
,如果此表访问频率较高,那么索引树中较高层的索引很可能在缓存中被找到。所以真正的
IO
可能小于上面的情况。
2
)聚集索引与插入操作
最简单的情况下,插入操作根据索引找到对应的数据页,然后通过挪动已有的记录为新数据腾出空间,最后插入数据。
如果数据页已满,则需要拆分数据页(页拆分是一种耗费资源的操作,一般数据库系统中会有相应的机制要尽量减少页拆分的次数,通常是通过为每页预留空间来实现):
A
)
在该使用的数据段(
extent
)上分配新的数据页,如果数据段已满,则需要分配新段。
B
)
调整索引指针,这需要将相应的索引页读入内存并加锁。
C
)
大约有一半的数据行被归入新的数据页中。
D
)
如果表还有非聚集索引,则需要更新这些索引指向新的数据页。
特殊情况:
A
)
如果新插入的一条记录包含很大的数据,可能会分配两个新数据页,其中之一用来存储新记录,另一存储从原页中拆分出来的数据。
B
)
通常数据库系统中会将重复的数据记录存储于相同的页中。
C
)
类似于自增列为聚集索引的,数据库系统可能并不拆分数据页,页只是简单的新添数据页。
3
)聚集索引与删除操作
删除行将导致其下方的数据行向上移动以填充删除记录造成的空白。
如果删除的行是该数据页中的最后一行,那么该数据页将被回收,相应的索引页中的记录将被删除。如果回收的数据页位于跟该表的其它数据页相同的段上,那么它可能在随后的时间内被利用。如果该数据页是该段的唯一一个数据页,则该段也被回收。
对于数据的删除操作,可能导致索引页中仅有一条记录,这时,该记录可能会被移至邻近的索引页中,原索引页将被回收,即所谓的“索引合并”。
非聚集索引与聚集索引相比:
A
)
叶子结点并非数据结点
B
)
叶子结点为每一真正的数据行存储一个
“
键
-
指针
”
对
C
)
叶子结点中还存储了一个指针偏移量,根据页指针及指针偏移量可以定位到具体的数据行。
D
)
类似的,在除叶结点外的其它索引结点,存储的也是类似的内容,只不过它是指向下一级的索引页的。
聚集索引是一种稀疏索引,数据页上一级的索引页存储的是页指针,而不是行指针。而对于非聚集索引,则是密集索引,在数据页的上一级索引页它为每一个数据行存储一条索引记录。
对于根与中间级的索引记录,它的结构包括:
A
)
索引字段值
B
)
RowId
(即对应数据页的页指针
+
指针偏移量)。在高层的索引页中包含
RowId
是为了当索引允许重复值时,当更改数据时精确定位数据行。
C
)
下一级索引页的指针
对于叶子层的索引对象,它的结构包括:
A
)
索引字段值
B
)
RowId
1
)非聚集索引与查询操作
针对上图,如果我们同样查找“
Green
”,那么一次查询操作将包含以下
IO
:
3
个索引页的读取
+1
个数据页的读取。
同样,由于缓存的关系,真实的
IO
实际可能要小于上面列出的。
2
)非聚集索引与插入操作
如果一张表包含一个非聚集索引但没有聚集索引,则新的数据将被插入到最末一个数据页中,然后非聚集索引将被更新。如果也包含聚集索引,该聚集索引将被用于查找新行将要处于什么位置,随后,聚集索引、以及非聚集索引将被更新。
3
)非聚集索引与删除操作
如果在
删除命令的
Where
子句中包含的列上,建有非聚集索引,那么该非聚集索引将被用于查找数据行的位置,数据删除之后,位于索引叶子上的对应记录也将被删除。如果该表上有其它非聚集索引,则它们叶子结点上的相应数据也要删除。
如果删除的数据是该数所页中的唯一一条,则该页也被回收,同时需要更新各个索引树上的指针。
由于没有自动的合并功能,如果应用程序中有频繁的随机删除操作,最后可能导致表包含多个数据页,但每个页中只有少量数据。
动作描述 使用聚集索引 使用非聚集索引
列经常被分组排序 应 应
返回某范围内的数据 应 不应
一个或极少不同值 不应 不应
小数目的不同值 应 不应
大数目的不同值 不应 应
频繁更新的列 不应 应
外键列 应 应
主键列 应 应
我们主要来看下:
聚集 非聚集
小数目的不同值 (树低,大块连续)(树低,多个数据页)
大数目的不同值 (树高,同一数据页,重建索引成本高) (树高,不同数据页,可以直接命中)
个人觉得,对于大数目的不同值建什么类型的索引,没有绝对那个好,那个不好。要看运用的场合。
主键和另外一个字段都是大数目的不同值 ,其它索引的查询量大时,不建议把主键设置成聚集索引,个人意见。
虽然我们想尽办法去优化数据库,优化数据库索引,但当数据量很大时,性能会快速下降。
这两个原因让我们去考虑用全文搜索引擎,比如lucene.
分享到:
相关推荐
数据库索引设计与优化是数据库管理系统中至关重要的一个环节,它直接影响到数据查询的效率、存储空间的使用以及系统的整体性能。在这个主题中,我们将深入探讨数据库索引的基础概念、设计原则、优化策略以及实际应用...
数据库索引设计与优化是数据库管理系统中的核心环节,它直接影响着数据查询的速度和系统的整体性能。索引在数据库中扮演着查找快照的角色,类似于书籍的目录,使得数据检索能够快速定位到目标信息,避免全表扫描,...
《Oracle与MySQL数据库索引设计与优化》这本书深入探讨了两个主流关系型数据库管理系统——Oracle和MySQL中的索引设计和优化策略。索引是数据库性能的关键因素,它们能够加速数据检索,提高系统效率,尤其在大数据量...
### 空间数据库索引技术的深度剖析 #### 核心知识点提炼: - **空间数据库索引技术的重要性**:空间数据库索引技术是提升空间数据库存储效率与空间检索性能的关键,尤其在处理大规模空间数据时更为显著。传统索引...
### Oracle数据库索引的维护 在Oracle数据库管理与优化的过程中,索引的维护是非常关键的一环。合理地创建、管理和优化索引能够显著提高查询性能,降低系统的响应时间,从而提升整个应用程序的效率。本文将从Oracle...
数据库索引是数据库性能优化的重要手段之一。创建索引可以提高查询速度,降低数据库的负载,提高数据的安全性。本文将详细介绍数据库创建索引的原则、分类、创建方法、管理和优化等方面的知识点。 索引的概念和优点...
Oracle 数据库索引优化方法探析是指通过对 Oracle 数据库索引的分析和优化,以提高数据库的查询效率和性能。 Oracle 数据库索引是一种数据结构,用于快速访问数据库表的特定信息。通过索引的小 I/O 操作可以替代大的...
数据库索引设计与优化是数据库管理系统中的重要环节,对于提升数据查询效率和系统性能具有决定性的作用。在大型数据处理和高并发应用中,合理的索引设计和优化策略显得尤为重要。本节将深入探讨数据库索引的基础知识...
【空间、时序、时空数据库索引技术的分析】 索引技术在数据库系统中起着至关重要的作用,尤其是在处理大量数据时,它能够提高查询效率,确保数据的快速定位。随着大数据时代的发展,数据库技术从关系数据库扩展到了...
因此,对MongoDB数据库索引构建情况进行全面分析至关重要,以确保系统性能与资源使用的平衡。 首先,我们可以通过`mongostat`工具来实时监测MongoDB的运行状态。`mongostat`每隔一段时间(默认是1秒)会输出各种...
Oracle数据库中的索引维护是数据库管理员日常工作中至关重要的一部分,尤其是在大型企业级应用中,高效的索引管理能够显著提升查询性能和数据库的整体效率。本文主要关注Oracle8i版本中的B-tree索引维护。 首先,...
本文《面向多核处理器的空间数据库索引性能分析》主要探讨了在多核处理器环境下,如何优化空间数据库的索引性能。作者吴烨、熊伟、蔡蕾和景宁来自国防科学技术大学电子科学与工程学院,他们在文章中针对R-Tree索引、...
本文将深入探讨数据库中的非聚集索引、聚集索引以及索引模式的概念,并分析它们之间的区别。 首先,让我们了解一下**非聚集索引**。非聚集索引在数据库中不按照数据的实际物理顺序存储。每个非聚集索引条目包含键值...
总结来说,数据库索引对于提升数据库的查询性能具有至关重要的作用,但是它的设计和优化需要根据具体的应用场景和需求进行精细的分析和管理。在设计数据库时,必须平衡索引所带来的益处和成本,合理地利用索引,才能...
《多核处理器环境下内存数据库索引性能分析》这篇文章主要探讨了在现代计算机硬件技术发展,特别是多核处理器广泛应用的背景下,内存数据库索引结构的性能表现。文章通过实验测试对比了B树、T树、CSS树和CSB树等经典...
MongoDB 数据库索引介绍 MongoDB 数据库索引是提高查询性能和减少查询时间的重要手段。索引可以告诉 MongoDB 如何高效地检索数据,以便快速地找到所需的数据。在本文中,我们将深入探讨 MongoDB 数据库索引的基础...
"基于SQL Server数据库索引的创建与优化分析" 本文主要介绍了SQL Server数据库索引的创建和优化分析。索引是数据库管理系统中负责排 序的数据结构,可以快速找到所要检索数据的物理存储地址,以便完成读取数据和...