목차
局部性原理与磁盘预读
B-/+Tree索引的性能分析

数据库索引详解

Jun 07, 2016 pm 03:47 PM
데이터 베이스 찾다 색인 상해 질문

说白了,索引问题就是一个查找问题。。。 数据库索引 ,是数据库管理系统中 一个排序的数据结构 ,以协助快速查询、更新数据库表中数据。 索引的实现通常使用B树及其变种B树 。 在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某

说白了,索引问题就是一个查找问题。。。


数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树

在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

为表设置索引要付出代价的:一是增加了数据库的存储空间二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动)

数据库索引详解

上图展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。


创建索引可以大大提高系统的性能。

第一,通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。

第二,可以大大加快数据的检索速度,这也是创建索引的最主要的原因。

第三,可以加速表和表之间的连接,特别是在实现数据的参考完整性方面特别有意义。

第四,在使用分组和排序子句进行数据检索时,同样可以显著减少查询中分组和排序的时间。

第五,通过使用索引,可以在查询的过程中,使用优化隐藏器,提高系统的性能。 


也许会有人要问:增加索引有如此多的优点,为什么不对表中的每一个列创建一个索引呢?因为,增加索引也有许多不利的方面。

第一,创建索引和维护索引要耗费时间,这种时间随着数据量的增加而增加。

第二,索引需要占物理空间,除了数据表占数据空间之外,每一个索引还要占一定的物理空间,如果要建立聚簇索引,那么需要的空间就会更大。

第三,当对表中的数据进行增加、删除和修改的时候,索引也要动态的维护,这样就降低了数据的维护速度。


索引是建立在数据库表中的某些列的上面。在创建索引的时候,应该考虑在哪些列上可以创建索引,在哪些列上不能创建索引。一般来说,应该在这些列上创建索引:在经常需要搜索的列上,可以加快搜索的速度;在作为主键的列上,强制该列的唯一性和组织表中数据的排列结构;在经常用在连接的列上,这些列主要是一些外键,可以加快连接的速度;在经常需要根据范围进行搜索的列上创建索引,因为索引已经排序,其指定的范围是连续的;在经常需要排序的列上创建索引,因为索引已经排序,这样查询可以利用索引的排序,加快排序查询时间;在经常使用在WHERE子句中的列上面创建索引,加快条件的判断速度。


同样,对于有些列不应该创建索引。一般来说,不应该创建索引的的这些列具有下列特点:

第一,对于那些在查询中很少使用或者参考的列不应该创建索引。这是因为,既然这些列很少使用到,因此有索引或者无索引,并不能提高查询速度。相反,由于增加了索引,反而降低了系统的维护速度和增大了空间需求。

第二,对于那些只有很少数据值的列也不应该增加索引。这是因为,由于这些列的取值很少,例如人事表的性别列,在查询的结果中,结果集的数据行占了表中数据行的很大比例,即需要在表中搜索的数据行的比例很大。增加索引,并不能明显加快检索速度。

第三,对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为,这些列的数据量要么相当大,要么取值很少。

第四,当修改性能远远大于检索性能时,不应该创建索引。这是因为,修改性能和检索性能是互相矛盾的。当增加索引时,会提高检索性能,但是会降低修改性能。当减少索引时,会提高修改性能,降低检索性能。因此,当修改性能远远大于检索性能时,不应该创建索引。


根据数据库的功能,可以在数据库设计器中创建三种索引:唯一索引、主键索引和聚集索引

唯一索引 

唯一索引是不允许其中任何两行具有相同索引值的索引。

当现有数据中存在重复的键值时,大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如,如果在employee表中职员的姓(lname)上创建了唯一索引,则任何两个员工都不能同姓。 主键索引 数据库表经常有一列或列组合,其值唯一标识表中的每一行。该列称为表的主键。 在数据库关系图中为表定义主键将自动创建主键索引,主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时,它还允许对数据的快速访问。 聚集索引 在聚集索引中,表中行的物理顺序与键值的逻辑(索引)顺序相同。一个表只能包含一个聚集索引。

如果某索引不是聚集索引,则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比,聚集索引通常提供更快的数据访问速度。



局部性原理与磁盘预读

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理当一个数据被用到时,其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

B-/+Tree索引的性能分析

到这里终于可以分析B-/+Tree索引的性能了。

上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析,根据B-Tree的定义,可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:

每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。


综上所述,用B-Tree作为索引结构效率是非常高的。



应该花时间学习B-树和B+树数据结构

=============================================================================================================

1)B树

B树中每个节点包含了键值和键值对于的数据对象存放地址指针,所以成功搜索一个对象可以不用到达树的叶节点。

成功搜索包括节点内搜索和沿某一路径的搜索,成功搜索时间取决于关键码所在的层次以及节点内关键码的数量。

在B树中查找给定关键字的方法是:首先把根结点取来,在根结点所包含的关键字K1,…,kj查找给定的关键字(可用顺序查找或二分查找法),若找到等于给定值的关键字,则查找成功;否则,一定可以确定要查的关键字在某个Ki或Ki+1之间,于是取Pi所指的下一层索引节点块继续查找,直到找到,或指针Pi为空时查找失败。

2)B+树

B+树非叶节点中存放的关键码并不指示数据对象的地址指针,非也节点只是索引部分。所有的叶节点在同一层上,包含了全部关键码和相应数据对象的存放地址指针,且叶节点按关键码从小到大顺序链接。如果实际数据对象按加入的顺序存储而不是按关键码次数存储的话,叶节点的索引必须是稠密索引,若实际数据存储按关键码次序存放的话,叶节点索引时稀疏索引。

B+树有2个头指针,一个是树的根节点,一个是最小关键码的叶节点。

所以 B+树有两种搜索方法:

一种是按叶节点自己拉起的链表顺序搜索。

一种是从根节点开始搜索,和B树类似,不过如果非叶节点的关键码等于给定值,搜索并不停止,而是继续沿右指针,一直查到叶节点上的关键码。所以无论搜索是否成功,都将走完树的所有层。

B+ 树中,数据对象的插入和删除仅在叶节点上进行。

这两种处理索引的数据结构的不同之处:
a,B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有可能重复出现,以维持B+树的平衡。
b,因为B树键位置不定,且在整个树结构中只出现一次,虽然可以节省存储空间,但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
c,B树的查询效率与键在树中的位置有关,最大时间复杂度与B+树相同(在叶结点的时候),最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

iOS 18에는 손실되거나 손상된 사진을 검색할 수 있는 새로운 '복구된' 앨범 기능이 추가되었습니다. iOS 18에는 손실되거나 손상된 사진을 검색할 수 있는 새로운 '복구된' 앨범 기능이 추가되었습니다. Jul 18, 2024 am 05:48 AM

Apple의 최신 iOS18, iPadOS18 및 macOS Sequoia 시스템 릴리스에는 사진 애플리케이션에 중요한 기능이 추가되었습니다. 이 기능은 사용자가 다양한 이유로 손실되거나 손상된 사진과 비디오를 쉽게 복구할 수 있도록 설계되었습니다. 새로운 기능에는 사진 앱의 도구 섹션에 '복구됨'이라는 앨범이 도입되었습니다. 이 앨범은 사용자가 기기에 사진 라이브러리에 포함되지 않은 사진이나 비디오를 가지고 있을 때 자동으로 나타납니다. "복구된" 앨범의 출현은 데이터베이스 손상으로 인해 손실된 사진과 비디오, 사진 라이브러리에 올바르게 저장되지 않은 카메라 응용 프로그램 또는 사진 라이브러리를 관리하는 타사 응용 프로그램에 대한 솔루션을 제공합니다. 사용자는 몇 가지 간단한 단계만 거치면 됩니다.

PHP에서 MySQLi를 사용하여 데이터베이스 연결을 설정하는 방법에 대한 자세한 튜토리얼 PHP에서 MySQLi를 사용하여 데이터베이스 연결을 설정하는 방법에 대한 자세한 튜토리얼 Jun 04, 2024 pm 01:42 PM

MySQLi를 사용하여 PHP에서 데이터베이스 연결을 설정하는 방법: MySQLi 확장 포함(require_once) 연결 함수 생성(functionconnect_to_db) 연결 함수 호출($conn=connect_to_db()) 쿼리 실행($result=$conn->query()) 닫기 연결( $conn->close())

PHP에서 데이터베이스 연결 오류를 처리하는 방법 PHP에서 데이터베이스 연결 오류를 처리하는 방법 Jun 05, 2024 pm 02:16 PM

PHP에서 데이터베이스 연결 오류를 처리하려면 다음 단계를 사용할 수 있습니다. mysqli_connect_errno()를 사용하여 오류 코드를 얻습니다. 오류 메시지를 얻으려면 mysqli_connect_error()를 사용하십시오. 이러한 오류 메시지를 캡처하고 기록하면 데이터베이스 연결 문제를 쉽게 식별하고 해결할 수 있어 애플리케이션이 원활하게 실행될 수 있습니다.

Golang에서 데이터베이스 콜백 함수를 사용하는 방법은 무엇입니까? Golang에서 데이터베이스 콜백 함수를 사용하는 방법은 무엇입니까? Jun 03, 2024 pm 02:20 PM

Golang의 데이터베이스 콜백 기능을 사용하면 다음을 달성할 수 있습니다. 지정된 데이터베이스 작업이 완료된 후 사용자 정의 코드를 실행합니다. 추가 코드를 작성하지 않고도 별도의 함수를 통해 사용자 정의 동작을 추가할 수 있습니다. 삽입, 업데이트, 삭제, 쿼리 작업에 콜백 함수를 사용할 수 있습니다. 콜백 함수를 사용하려면 sql.Exec, sql.QueryRow, sql.Query 함수를 사용해야 합니다.

JSON 데이터를 Golang의 데이터베이스에 저장하는 방법은 무엇입니까? JSON 데이터를 Golang의 데이터베이스에 저장하는 방법은 무엇입니까? Jun 06, 2024 am 11:24 AM

JSON 데이터는 gjson 라이브러리 또는 json.Unmarshal 함수를 사용하여 MySQL 데이터베이스에 저장할 수 있습니다. gjson 라이브러리는 JSON 필드를 구문 분석하는 편리한 방법을 제공하며, json.Unmarshal 함수에는 JSON 데이터를 비정렬화하기 위한 대상 유형 포인터가 필요합니다. 두 방법 모두 SQL 문을 준비하고 삽입 작업을 수행하여 데이터를 데이터베이스에 유지해야 합니다.

MySQL : 쉽게 학습하기위한 간단한 개념 MySQL : 쉽게 학습하기위한 간단한 개념 Apr 10, 2025 am 09:29 AM

MySQL은 오픈 소스 관계형 데이터베이스 관리 시스템입니다. 1) 데이터베이스 및 테이블 작성 : CreateAbase 및 CreateTable 명령을 사용하십시오. 2) 기본 작업 : 삽입, 업데이트, 삭제 및 선택. 3) 고급 운영 : 가입, 하위 쿼리 및 거래 처리. 4) 디버깅 기술 : 확인, 데이터 유형 및 권한을 확인하십시오. 5) 최적화 제안 : 인덱스 사용, 선택을 피하고 거래를 사용하십시오.

PHP 데이터베이스 연결 함정: 일반적인 실수와 오해를 피하세요 PHP 데이터베이스 연결 함정: 일반적인 실수와 오해를 피하세요 Jun 05, 2024 pm 10:21 PM

PHP 데이터베이스 연결 오류를 방지하려면 연결 오류를 확인하고 변수 이름을 자격 증명과 일치시키는 모범 사례를 따르십시오. 자격 증명을 하드코딩하지 않으려면 보안 저장소나 환경 변수를 사용하세요. SQL 주입을 방지하기 위해 사용 후 연결을 닫고 준비된 문 또는 바인딩된 매개 변수를 사용합니다.

상위 10 개 글로벌 디지털 가상 통화 거래 플랫폼 순위 (2025 권위있는 순위) 상위 10 개 글로벌 디지털 가상 통화 거래 플랫폼 순위 (2025 권위있는 순위) Mar 06, 2025 pm 04:36 PM

2025 년에 Global Digital Virtual Currency Trading Platform은 2025 년에 트랜잭션 볼륨, 보안 및 사용자 경험과 같은 지표를 기반으로 전 세계 10 대 디지털 가상 통화 거래 플랫폼을 권위있게 발표합니다. OKX는 강력한 기술 강점과 글로벌 운영 전략으로 1 위를 차지했으며 Binance는 높은 유동성과 낮은 수수료와 밀접한 관련이 있습니다. Gate.io, Coinbase 및 Kraken과 같은 플랫폼은 각각의 장점과 함께 최전선에 있습니다. 이 목록에는 Huobi, Kucoin, Bitfinex, Crypto.com 및 Gemini와 같은 거래 플랫폼이 각각 고유 한 특성을 지니고 있지만 투자는 신중해야합니다. 플랫폼을 선택하려면 보안, 유동성, 수수료, 사용자 경험, 통화 선택 및 규제 준수와 같은 요소를 고려해야합니다.

See all articles