《数据库索引原理》由会员分享，可在线阅读，更多相关《数据库索引原理（9页珍藏版）》请在金锄头文库上搜索。
1、数据库索引原理SQL SERVER (下称SQLS)为例，将数据库管理中难于理解的“索引原理”问题给各位朋友作一个深入浅出的介绍。其他的数据 库管理系统如Oracle、Sybase等，朋友们可以融会贯通，举一反三。一、数据表的基本结构建立数据库的目的是管理大量数据，而建立索引的目的就是提高数据检索效率，改善数据库工作性能，提高数据访问速度。对于 索引，我们要知其然，更要知其所以然，关键在于认识索引的工作原理，才能更好的管理索引。为认识索引工作原理，首先有必要对 数据表的基本结构作一次全面的复习。SQLS当一个新表被创建之时，系统将在磁盘中分配一段以8K为单位的连续空间，当字段的值从内存写入磁盘
2、时，就在这一既 定空间随机保存，当一个8K用完的时候，SQLS指针会自动分配一个8K的空间。这里，每个8K空间被称为一个数据页(Page), 又名页面或数据页面，并分配从0-7的页号，每个文件的第0页记录引导信息，叫文件头(File header)；每8个数据页(64K)的组 合形成扩展区(Extent)，称为扩展。全部数据页的组合形成堆(Heap)。SQLS规定行不能跨越数据页，所以，每行记录的最大数据量只能为8K。这就是char和varchar这两种字符串类型容量要限制 在8K以内的原因，存储超过8K的数据应使用text类型，实际上，text类型的字段值不能直接录入和保存，它只是存储一个指
3、针，指 向由若干8K的文本数据页所组成的扩展区，真正的数据正是放在这些数据页中。页面有空间页面和数据页面之分。当一个扩展区的8个数据页中既包含了空间页面又包括了数据或索引页面时，称为混合扩展(Mixed Extent)，每张表都以混合扩展开 始；反之，称为一致扩展(Uniform Extent)，专门保存数据及索引信息。表被创建之时，SQLS在混合扩展中为其分配至少一个数据页面，随着数据量的增长，SQLS可即时在混合扩展中分配出7个页面， 当数据超过8个页面时，则从一致扩展中分配数据页面。空间页面专门负责数据空间的分配和管理，包括：PFS页面(Page free space):记录一个页面是否
4、已分配、位于混合扩展还是一致 扩展以及页面上还有多少可用空间等信息；GAM页面(Global allocation map)和SGAM页面(Secodary global allocation map)：用 来记录空闲的扩展或含有空闲页面的混合扩展的位置。SQLS综合利用这三种类型的页面文件在必要时为数据表创建新空间；数据页或索引页则专门保存数据及索引信息，SQLS使用4种类型的数据页面来管理表或索引：它们是IAM页、数据页、文本/图像页 和索引页。在WINDOWS中，我们对文件执行的每一步操作，在磁盘上的物理位置只有系统(system)才知道；SQL SERVER沿袭了这种工作 方式，在插入
5、数据的过程中，不但每个字段值在数据页面中的保存位置是随机的，而且每个数据页面在堆”中的排列位置也只有系统(system )才知道。这是为什么呢？众所周知，OS之所以能管理DISK，是因为在系统启动时首先加载了文件分配表：FAT(File Allocation Table)，正 是由它管理文件系统并记录对文件的一切操作，系统才得以正常运行；同理，作为管理系统级的SQL SERVER,也有这样一张类似 FAT的表存在，它就是索引分布映像页:IAM(Index Allocation Map)。IAM的存在，使SQLS对数据表的物理管理有了可能。IAM页从混合扩展中分配，记录了 8个初始页面的位置和该
6、扩展区的位置，每个IAM页面能管理512,000个数据页面，如果数据量太 大，SQLS也可以增加更多的IAM页，可以位于文件的任何位置。第一个IAM页被称为FirstlAM,其中记录了以后的IAM页的位置。数据页和文本/图像页互反，前者保存非文本/图像类型的数据，因为它们都不超过8K的容量，后者则只保存超过8K容量的文本或图 像类型数据。而索引页顾名思义，保存的是与索引结构相关的数据信息。了解页面的问题有助我们下一步准确理解SQLS维护索引的 方式，如页拆分、填充因子等。二、索引的基本概念索引是一种特殊类型的数据库对象，它与表有着密切的联系。索引是为检索而存在的。如一些书籍的末尾就专门附有索引
7、，指明了某个关键字在正文中的出现的页码位置，方便我们查找，但大多 数的书籍只有目录，目录不是索引，只是书中内容的排序，并不提供真正的检索功能。可见建立索引要单独占用空间；索引也并不是 必须要建立的，它们只是为更好、更快的检索和定位关键字而存在。再进一步说，我们要在图书馆中查阅图书，该怎么办呢？图书馆的前台有很多叫做索引卡片柜的小柜子，里面分了若干的类别供我们 检索图书，比如你可以用书名的笔画顺序或者拼音顺序作为查找的依据，你还可以从作者名的笔画顺序或拼音顺序去查询想要的图书， 反正有许多检索方式，但有一点很明白，书库中的书并没有按照这些卡片柜中的顺序排歹I一虽然理论上可以这样做，事实上，所有
8、图书的脊背上都人工的粘贴了一个特定的编号，它们是以这个顺序在排列。索引卡片中并没有指明这本书摆放在书库中的第几个书 架的第几本，仅仅指明了这个特定的编号。管理员则根据这一编号将请求的图书返回到读者手中。这是很形象的例子，以下的讲解将 会反复用到它。SQLS在安装完成之后，安装程序会自动创建master、model、tempdb等几个特殊的系统数据库，其中master是SQLS的主数据库, 用于保存和管理其它系统数据库、用户数据库以及SQLS的系统信息，它在SQLS中的地位与WINDOWS下的注册表相当。master中有一个名为sysindexes的系统表，专门管理索引。SQLS查询数据表的操作
9、都必须用到它，毫无疑义，它是本文主角之一。查看一张表的索引属性，可以在查询分析器中使用以下命令：select * from sysindexes where id=object_id(tablename)；而要查看表 的索引所占空间的大小，可以使用系统存储过程命令：sp_spaceused tablename，其中参数tablename为被索引的表名。如果你通过书后的索引知道了一个关键字所在的页码，你有可能通过随机的翻寻，最终到达正确的页码。但更科学更快捷的方法是： 首先把书翻到大概二分之一的位置，如果要找的页码比该页的页码小，就把书向前翻到四分之一处，否则，就把书向后翻到四分之三 的地方，依
10、此类推，把书页续分成更小的部分，直至正确的页码。这叫两分法”，微软在官方教程MOC里另有一种说法：叫B树(B-Tree，Balance Tree)，即平衡树。一个表索引由若干页面组成，这些页面构成了一个树形结构。B树由“根”(root)开始，称为根级节点，它通过指向另外两个页，把一 个表的记录从逻辑上分成两个部分：“枝”一-非叶级节点(Non-Leaf Level)；而非叶级节点又分别指向更小的部分：“叶”叶级节 点(Leaf Level)o根节点、非叶级节点和叶级节点都位于索引页中，统称为索引节点，属于索引页的范筹。这些枝、“叶”最终指向 了具体的数据页(Page)。在根级节点和叶级节点之间
11、的叶又叫数据中间页。“根” (root)对应了 sysindexes表的Root字段，其中记载了非叶级节点的物理位置(即指针)；非叶级节点位于根节点和叶节点之间, 记载了指向叶级节点的指针；而叶级节点则最终指向数据页。这就是平衡树。四、聚集索引和非聚集索引从形式上而言，索引分为聚集索引(Clustered Indexes)和非聚集索引(NonClustered Indexes)。聚集索引相当于书籍脊背上那个特定的编号。如果对一张表建立了聚集索引，其索引页中就包含着建立索引的列的值(下称索引键 值)，那么表中的记录将按照该索引键值进行排序。比如，我们如果在姓名”这一字段上建立了聚集索引，则表中的
12、记录将按照姓名 进行排列；如果建立了聚集索引的列是数值类型的，那么记录将按照该键值的数值大小来进行排列。非聚集索引用于指定数据的逻辑顺序，也就是说，表中的数据并没有按照索引键值指定的顺序排列，而仍然按照插入记录时的顺序存 放。其索引页中包含着索引键值和它所指向该行记录在数据页中的物理位置，叫做行定位符(RID： Row ID)。好似书后面的的索引 表，索引表中的顺序与实际的页码顺序也是不一致的。而且一本书也许有多个索引。比如主题索引和作者索引。SQL Server在默认的情况下建立的索引是非聚集索引，由于非聚集索引不对表中的数据进行重组，而只是存储索引键值并用一个指针 指向数据所在的页面。一个
13、表如果没有聚集索引时，理论上可以建立249个非聚集索引。每个非聚集索引提供访问数据的不同排序顺序。五、数据是怎样被访问的若能真正理解了以上索引的基础知识，那么再回头来看索引的工作原理就简单和轻松多了。(一) SQLS怎样访问没有建立任何索引数据表：Heap译成汉语叫做“堆”，其本义暗含杂乱无章、无序的意思，前面提到数据值被写进数据页时，由于每一行记录之间并没地有特定的 排列顺序，所以行与行的顺序就是随机无序的，当然表中的数据页也就是无序的了，而表中所有数据页就形成了“堆”，可以说，一张 没有索引的数据表，就像一个只有书柜而没有索引卡片柜的图书馆，书库里面塞满了一堆乱七八糟的图书。当读者对管理员
14、提交查询 请求后，管理员就一头钻进书库，对照查找内容从头开始一架一柜的逐本查找，运气好的话，在第一个书架的第一本书就找到了，运 气不好的话，要到最后一个书架的最后一本书才找到。SQLS在接到查询请求的时候，首先会分析sysindexes表中一个叫做索引标志符(INDID: Index ID)的字段的值，如果该值为0表示 这是一张数据表而不是索引表，SQLS就会使用sysindexes表的另一个字段也就是在前面提到过的FirstIAM值中找到该表的IAM页链一一也就是所有数据页集合。这就是对一个没有建立索引的数据表进行数据查找的方式，是不是很没效率？对于没有索引的表，对于一堆”这样的记录，SQL
15、S也 只能这样做，而且更没劲的是，即使在第一行就找到了被查询的记录，SQLS仍然要从头到尾的将表扫描一次。这种查询称为“遍历”， 又叫“表扫描”。可见没有建立索引的数据表照样可以运行，不过这种方法对于小规模的表来说没有什么太大的问题，但要查询海量的数据效率就太低 了。(二) SQLS怎样访问建立了非聚集索引的数据表：如前所述，非聚集索引可以建多个，具有B树结构，其叶级节点不包含数据页，只包含索引行。假定一个表中只有非聚集索引，则每个 索引行包含了非聚集索引键值以及行定位符(ROW ID,RID)，他们指向具有该键值的数据行。每一个RID由文件ID、页编号和在页 中行的编号组成。当INDID的值
16、在2-250之间时，意味着表中存在非聚集索引页。此时，SQLS调用ROOT字段的值指向非聚集索引B树的ROOT, 在其中查找与被查询最相近的值，根据这个值找到在非叶级节点中的页号，然后顺藤摸瓜，在叶级节点相应的页面中找到该值的RID, 最后根据这个RID在Heap中定位所在的页和行并返回到查询端。例如：假定在Lastname上建立了非聚集索引，则执行Select * From Member Where Lastname=Ota时，查询过程是：SQLS查询INDID值为2；立即从根出发，在非叶级节点中定位最接近Ota的值“Martin”，并查到其位于叶级页面的第61页；仅在叶级页 面的第61页的Martin下搜寻Ota的RID，其RID显示为N：706：4，表示Lastname字段中名为Ota的记录位于堆的第707页的第4 行，N表示文件的ID值，与数据无关；根据上述信息，S
