《数据库原理与实用技术》第八章 Indexing索引.pdfVIP

Chapter 8 IndexingChapter 8 Indexing 有需要word版格式的可索取 Indexing 8.1 The Concept of Indexing 8.2 Disk Storage 8.3 The B-Tree Index 8.4 Clustered and Non-Clustered Indexes 8.5 A Hash Primary Index 8.6 Throwing Darts at Random Slots Indexing Introduction  当一个 S Q L查询提交给数据库系统的时候，一个称 为查询优化器(query optimizer)的软件模块将对查询 中的非过程命令进行分析，然后决定一个能一步一步 地访问到所需数据的步骤。这种执行查询的步骤被人 们称为访问计划(access plan)或者查询计划(query plan)。 在第9章中，我们将详细讨论查询优化器是怎么制定出 访问计划的；在本章中，我们主要阐述查询如何利用 数据库索引(database indexes)来提高访问表中数据 的效率。 8.1 The Concept of Indexing Introduction 数据库索引，简称为索引，与读者以前学习过的驻留 内存的数据结构(如：二叉树、B树和散列表)有些类似。 它的目的是提高对表中行数据进行查找的效率。 数据库索引区别于驻留内存的数据结构的地方在于， 数据库索引包含的数据量比一次能调入内存的数据量 大。因此，数据库索引的数据是存放在磁盘上的，只 有被访问的时候才会被部分地调入内存。 这样做的优点是，当计算机关闭的时候，驻留内存的 数据将丢失，但是数据库索引中的数据项表中的记录 一样会永久存在。 8.1 The Concept of Indexing Introduction 索引是由一系列存储在磁盘上的索引项组成。一个索引项 对应于索引中的一行，当行发生更新的时候，索引也将做 出响应。 索引项有点儿像一个由两列组成的表：第一列是索引键 ， 由行中某些列 （通常是一列）中的值串接而成；第二列是 行指针，指向行所在的磁盘位置。 索引项存储磁盘上，通常是按照索引键排序的 （尽管有的 时候可能是按散列访问），这样就可以提高特定SELECT 语句的查询速度。 8.1 The Concept of Indexing Introduction 数据库索引通常是存放在磁盘上的，但是和访问内存 相比，磁盘访问是相当慢的。 数据库索引设计的最重要的目标就是要减少读数据所 需的磁盘访问的次数。  [8.1.1] select * from customers where city=Boston and discnt between 12 and 14 查询优化器将要决 定怎样从 customers表中访 问到上述查询所需 的行。 8.1 The Concept of Indexing Introduction  [8.1.1] select * from customers where city=Boston and discnt between 12 and 14;  [方法一]执行一次表扫描 ，将对表中所有行进行连续访问， 把那些不满足 WHERE 子句中的两个 And 的谓词的行剔 除。  [方法二]city上有索引，而discnt上无索引。首先系统将 查询在 Boston的顾客，然后通过上面讲述的行指针来访