由浅入深理解索引的实现

这篇文章是介绍MySQL数据库中的索引是如何根据需求一步步演变最终成为B+树结构的以及针对B+树索引的查询,插入,删除,更新等操作的处理方法。Oracle和DB2数据库索引的实现基本上也是大同小异的。文章写得很通俗易懂,就转在这了。关于B+树和索引内部结构可以参考:《B 树、B- 树、B+ 树和B* 树》和《深入理解DB2索引(Index)》。


00 – 背景知识

– B-Tree & B+Tree

  http://en.wikipedia.org/wiki/B%2B_tree
  http://en.wikipedia.org/wiki/B-tree

– 折半查找(Binary Search)

  http://en.wikipedia.org/wiki/Binary_search_algorithm

– 数据库的性能问题

  A. 磁盘IO性能非常低,严重的影响数据库系统的性能。
  B. 磁盘顺序读写比随机读写的性能高很多。

– 数据的基本存储结构

  A. 磁盘空间被划分为许多大小相同的块(Block)或者页(Page).
  B. 一个表的这些数据块以链表的方式串联在一起。
  C. 数据是以行(Row)为单位一行一行的存放在磁盘上的块中,如图所示.
  D. 在访问数据时,一次从磁盘中读出或者写入至少一个完整的Block。

                                              Fig. 1


01 – 数据基本操作的实现

  基本操作包括:INSERT、UPDATE、DELETE、SELECT。

– SELECT

  A. 定位数据
  B. 读出数据所在的块,对数据加工
  C. 返回数据给用户

– UPDATE、DELETE

  A. 定位数据
  B. 读出数据所在的块,修改数据
  C. 写回磁盘

– INSERT

  A. 定位数据要插入的页(如果数据需要排序)
  B. 读出要插入的数据页,插入数据.
  C. 写回磁盘

如何定位数据?
– 表扫描(Table Scan)

  A. 从磁盘中依次读出所有的数据块,一行一行的进行数据匹配。
  B. 时间复杂度 是O(n), 如果所有的数据占用了100个块。尽管只查询一行数据,
     也需要读出所有100个块的数据。
  C. 需要大量的磁盘IO操作,极大的影响了数据定位的性能。

因为数据定位操作是所有数据操作必须的操作,数据定位操作的效率会直接影响所有的数据操作的效率。
因此我们开始思考,如何来减少磁盘的IO?
– 减少磁盘IO

  A. 减少数据占用的磁盘空间
     压缩算法、优化数据存储结构
  B. 减少访问数据的总量
     读出或写入的数据中,有一部分是数据操作所必须的,这部分称作有效数据。剩余的
     部分则不是数据操作必须的数据,称为无效数据。例如,查询姓名是‘张三’的记录。
     那么这条记录是有效记录,其他记录则是无效记录。我们要努力减少无效数据的访问。

02 – 索引的产生

– 键(Key)

  首先,我们发现在多数情况下,定位操作并不需要匹配整行数据。而是很规律的只匹配某一个
  或几个列的值。 例如,图中第1列就可以用来确定一条记录。这些用来确定一条数据的列,统 
  称为键(Key).

                    Fig. 2

– Dense Index

  根据减少无效数据访问的原则,我们将键的值拿过来存放到独立的块中。并且为每一个键值添
  加一个指针, 指向原来的数据块。如图所示,


  •                             Fig. 3

  这就是‘索引’的祖先Dense Index. 当进行定位操作时,不再进行表扫描。而是进行
  索引扫描(Index Scan),依次读出所有的索引块,进行键值的匹配。当找到匹配的键值后,
  根据该行的指针直接读取对应的数据块,进行操作。假设一个块中能存储100行数据,
  10,000,000行的数据需要100,000个块的存储空间。假设键值列(+指针)占用一行数据
  1/10的空间。那么大约需要10,000个块来存储Dense索引。因此我们用大约1/10的额外存储
  空间换来了大约全表扫描10倍的定位效率。

03 – 索引的进化

  在实际的应用中,这样的定位效率仍然不能满足需求。很多人可能已经想到了,通过排序和查找
  算法来减少IO的访问。因此我们开始尝试对Dense Index进行排序存储,并且期望利用排序查
  找算法来减少磁盘IO。

– 折半块查找

  A. 对Dense Index排序
  B. 需要一个数组按顺序存储索引块地址。以块为单位,不存储所有的行的地址。
  C. 这个索引块地址数组,也要存储到磁盘上。将其单独存放在一个块链中,如下图所示。
  D. 折半查找的时间复杂度是O(log 2(N))。在上面的列子中,dense索引总共有10,000个块。假设1个块
     能存储2000个指针,需要5个块来存储这个数组。通过折半块查找,我们最多只需要读取
     5(数组块)+ 14(索引块log 2(10000))+1(数据块)=20个块。


  •                                                                 Fig. 4

 – Sparse Index

  实现基于块的折半查找时发现,读出每个块后只需要和第一行的键值匹配,就可以决定下一个块
  的位置(方向)。 因此有效数据是每个块(最后一个块除外)的第一行的数据。还是根据减少无
  效数据IO的原则,将每一个块的第一行的数据单独拿出来,和索引数组的地址放到一起。这样就
  可以直接在这个数组上进行折半查找了。如下图所示,这个数组就进化成了Sparse Index

  •                                                         Fig. 5

  因为Sparse Index和Dense Index的存储结构是相同的,所以占用的空间也相同。大约需
  要10个块来存储10000个Dense Index块的地址和首行键值。通过Sparse索引,仅需要读
  取10(Sparse块)+1(Dense块)+1(数据块)=12个块.

– 多层Sparse Index

  因为Sparse Index本身是有序的,所以可以为Sparse Index再建sparse Index。通过
  这个方法,一层一层的建立 Sparse Indexes,直到最上层的Sparse Index只占用一个块
  为止,如下图所示.


  •                                        Fig. 6

  A. 这个最上层的Sparse Index称作整个索引树的根(root).
  B. 每次进行定位操作时,都从根开始查找。
  C. 每层索引只需要读出一个块。
  D. 最底层的Dense Index或数据称作叶子(leaf).
  E. 每次查找都必须要搜索到叶子节点,才能定位到数据。
  F. 索引的层数称作索引树的高度(height).
  G. 索引的IO性能和索引树的高度密切相关。索引树越高,磁盘IO越多。

  在我们的例子中的Sparse Index,只有10个块,因此我们只需要再建立一个Sparse Index.
  通过两层Sparse Index和一层Dense Index查找时,只需读取1+1+1+1=4个块。

– Dense Index和Sparse Index的区别

  A. Dense Index包含所有数据的键值,但是Sparse Index仅包含部分键值。
     Sparse Index占用更少的磁盘空间。
  B. Dense Index指向的数据可以是无序的,但是Sparse Index的数据必须是有序的。
  C. Sparse Index 可以用来做索引的索引,但是Dense Index不可以。
  D. 在数据是有序的时候,Sparse Index更有效。因此Dense Index仅用于无序的数据。
  E. 索引扫描(Index Scan)实际上是对Dense Index层进行遍历。

– 簇索引(Clustered Index)和辅助索引(Secondary Index)

  如果数据本身是基于某个Key来排序的,那么可以直接在数据上建立sparse索引,
  而不需要建立一个dense索引层(可以认为数据就是dense索引层)。 如下图所示:

  •                                                 Fig. 7

  这个索引就是我们常说的“Clustered Index”,而用来排序数据的键叫做主键Primary Key.

  A. 一个表只能有一个Clustered Index,因为数据只能根据一个键排序.
  B. 用其他的键来建立索引树时,必须要先建立一个dense索引层,在dense索引层上对此键的值
     进行排序。这样的索引树称作Secondary Index.
  C. 一个表上可以有多个Secondary Index.
  D. 对簇索引进行遍历,实际上就是对数据进行遍历。因此簇索引的遍历效率比辅组索引低。
     如SELECT count(*) 操作,使用辅组索引遍历的效率更高。

– 范围搜索(Range Search)

  由于键值是有序的,因此可以进行范围查找。只需要将数据块、Dense Index块分别以双向链表
  的方式进行连接, 就可以实现高效的范围查找。如下图所示:

  •                                                 Fig. 8

  •   范围查找的过程:

  •   A. 选择一个合适的边界值,定位该值数据所在的块

  •   B. 然后选择合适的方向,在数据块(或Dense Index块)链中进行遍历。

  •   C. 直到数据不满足另一个边界值,结束范围查找。

  • 是不是看着这个索引树很眼熟?换个角度看看这个图吧!

        Fig. 9

    • 这分明就是传说中的B+Tree.

    • – 索引上的操作

    •   A. 插入键值

    •   B. 删除键值

    •   C. 分裂一个节点

    •   D. 合并两个节点

    • 这些操作在教科书上都有介绍,这里就不介绍了。

    • 先写到这吧,实在写不动了,想明白容易,写明白就难了。下一篇里,打算谈谈标准B+Tree的几个问题,以及在

    • 实现过程中,B+Tree的一些变形。

    教科书上的B+Tree是一个简化了的,方便于研究和教学的B+Tree。然而在数据库实现时,为了
    更好的性能或者降低实现的难度,都会在细节上进行一定的变化。下面以InnoDB为例,来说说
    这些变化。

    04 – Sparse Index中的数据指针

      在“由浅入深理解索引的实现(1)”中提到,Sparse Index中的每个键值都有一个指针指向
      所在的数据页。这样每个B+Tree都有指针指向数据页。如图Fig.10所示:

    Fig.10

      如果数据页进行了拆分或合并操作,那么所有的B+Tree都需要修改相应的页指针。特别是
      Secondary B+Tree(辅助索引对应的B+Tree), 要对很多个不连续的页进行修改。同时也需要对
      这些页加锁,这会降低并发性。

      为了降低难度和增加更新(分裂和合并B+Tree节点)的性能,InnoDB 将 Secondary B+Tree中
      的指针替换成了主键的键值。如图Fig.11所示:

    Fig.11

      这样就去除了Secondary B+Tree对数据页的依赖,而数据就变成了Clustered B+Tree(簇
      索引对应的B+Tree)独占的了。对数据页的拆分及合并操作,仅影响Clustered B+Tree. 因此
      InnoDB的数据文件中存储的实际上就是多个孤立B+Tree。

      一个有趣的问题,当用户显式的把主键定义到了二级索引中时,还需要额外的主键来做二级索引的
      数据吗(即存储2份主键)? 很显然是不需要的。InnoDB在创建二级索引的时候,会判断主键的字段
      是否已经被包含在了要创建的索引中。

      接下来看一下数据操作在B+Tree上的基本实现。

    – 用主键查询

      直接在Clustered B+Tree上查询。

    – 用辅助索引查询
      A. 在Secondary B+Tree上查询到主键。
      B. 用主键在Clustered B+Tree

    可以看出,在使用主键值替换页指针后,辅助索引的查询效率降低了。
      A. 尽量使用主键来查询数据(索引遍历操作除外).
      B. 可以通过缓存来弥补性能,因此所有的键列,都应该尽量的小。

    – INSERT
      A. 在Clustered B+Tree上插入数据
      B. 在所有其他Secondary B+Tree上插入主键。

    – DELETE
      A. 在Clustered B+Tree上删除数据。
      B. 在所有其他Secondary B+Tree上删除主键。

    – UPDATE 非键列
      A. 在Clustered B+Tree上更新数据。

    – UPDATE 主键列
      A. 在Clustered B+Tree删除原有的记录(只是标记为DELETED,并不真正删除)。
      B. 在Clustered B+Tree插入新的记录。
      C. 在每一个Secondary B+Tree上删除原有的数据。(有疑问,看下一节。)
      D. 在每一个Secondary B+Tree上插入原有的数据。

    – UPDATE 辅助索引的键值
      A. 在Clustered B+Tree上更新数据。
      B. 在每一个Secondary B+Tree上删除原有的主键。
      C. 在每一个Secondary B+Tree上插入原有的主键。

    更新键列时,需要更新多个页,效率比较低。
      A. 尽量不用对主键列进行UPDATE操作。
      B. 更新很多时,尽量少建索引。

    05 – 非唯一键索引

      教科书上的B+Tree操作,通常都假设”键值是唯一的“。但是在实际的应用中Secondary Index是允
      许键值重复的。在极端的情况下,所有的键值都一样,该如何来处理呢?
      InnoDB 的 Secondary B+Tree中,主键也是此键的一部分。
      Secondary Key = 用户定义的KEY + 主键。如图Fig.12所示:

    Fig.12

      注意主键不仅做为数据出现在叶子节点,同时也作为键的一部分出现非叶子节点。对于非唯一键来说,
      因为主键是唯一的,Secondary Key也是唯一的。当然,在插入数据时,还是会根据用户定义的Key,
      来判断唯一性。按理说,如果辅助索引是唯一的(并且所有字段不能为空),就不需要这样做。可是,
      InnoDB对所有的Secondary B+Tree都这样创建。

    还没弄明白有什么特殊的用途?有知道的朋友可以帮忙解答一下。
    也许是为了降低代码的复杂性,这是我想到的唯一理由。

    弄清楚了,即便是非空唯一键,在二级索引的B+Tree中也可能重复,因此必须要将主键加入到非叶子节点。

    06 – <Key, Pointer>对

      标准的B+Tree的每个节点有K个键值和K+1个指针,指向K+1个子节点。如图Fig.13:

    Fig.13(图片来自于WikiPedia)

      而在“由浅入深理解索引的实现(1)”中Fig.9的B+Tree上,每个节点有K个键值和K个指针。
      InnoDB的B+Tree也是如此。如图Fig.14所示:

    Fig.14

      这样做的好处在于,键值和指针一一对应。我们可以将一个<Key,Pointer>对看作一条记录。
      这样就可以用数据块的存储格式来存储索引块。因为不需要为索引块定义单独的存储格式,就
      降低了实现的难度。

    – 插入最小值

      当考虑在变形后的B+Tree上进行INSERT操作时,发现了一个有趣的问题。如果插入的数据的健
      值比B+Tree的最小键值小时,就无法定位到一个适当的数据块上去(<Key,Pointer>中的Key
      代表了子节点上的键值是>=Key的)。例如,在Fig.5的B+Tree中插入键值为0的数据时,无法
      定位到任何节点。

      在标准的B+Tree上,这样的键值会被定位到最左侧的节点上去。这个做法,对于Fig.5中的
      B+Tree也是合理的。Innodb的做法是,将每一层(叶子层除外)的最左侧节点的第一条记录标
      记为最小记录(MIN_REC).在进行定位操作时,任何键值都比标记为MIN_REC的键值大。因此0
      会被插入到最左侧的记录节点上。如Fig.15所示:

                                                   Fig.15

    07 – 顺序插入数据

      Fig.16是B-Tree的插入和分裂过程,我们看看有没有什么问题?

    Fig.16(图片来自于WikiPedia)

      标准的B-Tree分裂时,将一半的键值和数据移动到新的节点上去。原有节点和新节点都保留一半
      的空间,用于以后的插入操作。当按照键值的顺序插入数据时,左侧的节点不可能再有新的数据插入。
      因此,会浪费约一半的存储空间。

      解决这个问题的基本思路是:分裂顺序插入的B-Tree时,将原有的数据都保留在原有的节点上。
      创建一个新的节点,用来存储新的数据。顺序插入时的分裂过程如Fig.17所示:

    Fig.17

      以上是以B-Tree为例,B+Tree的分裂过程类似。InnoDB的实现以这个思路为基础,不过要复杂
      一些。因为顺序插入是有方向性的,可能是从小到大,也可能是从大到小的插入数据。所以要区
      分不同的情况。如果要了解细节,可参考以下函数的代码。
        btr_page_split_and_insert();
        btr_page_get_split_rec_to_right();
        btr_page_get_split_rec_to_right();

    InnoDB的代码太复杂了,有时候也不敢肯定自己的理解是对的。因此写了一个小脚本,来打印InnoDB数

    据文件中B+Tree。这样可以直观的来观察B+Tree的结构,验证自己的理解是否正确。

    ibd-analyzer.tar

  • 很多知识来自于下面这两本书。

  • Database Systems: The Complete Book (2nd Edition) ”

    “Transaction Processing: Concepts and Techniques”

深入理解DB2索引(Index)

索引(Index)是数据库管理系统中一个非常重要的数据结构,索引的合理使用能够极大提高数据库系统的性能。那么,什么是索引?索引有时如何提高数据库系统性能的呢?

阅读本文时建议参考:深入理解数据库磁盘存储(Disk Storage)

索引概念

以一本书为例,通常一本书开头会有目录,而后才是正文,通过目录中每行左侧的标题和右侧的页码,我们可以快速定位到需要阅读的页面,而无需一页一页翻阅到该页面。数据库中的索引就像目录,它能帮助数据库管理系统快速定位到表中符合查询条件的数据行。索引实际上也是数据表的组成部分之一(数据表的存储包括数据页面+索引页面)

定义:数据库索引实际上是一个单独的、物理的数据库结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针的清单(序列)

从索引的定义中可以得到:

1.索引是一个物理数据结构,也就是说,它是需要保持到物理磁盘上的,和普通的表数据一样要占用磁盘空间,也是存储在数据页上的。

2.索引是一个清单(或者说序列),由两部分组成:数据库表中的一列或多利的列值的集合、指向这些列值的数据页的逻辑指针。

可以把索引看作是一张只有两列的表,一列是普通数据表的列值(key-value),另一列是该列值的行对应的数据页的逻辑指针(Row-Pointer),这个逻辑指针可以理解为就是RID。需要说明的是,根据数据库产品和索引类型的不同,逻辑指针的结构也各不相同。如下图是索引的一个概览性描述,右侧是数据表页,左侧是对应的索引页。还有一点,从图上可以看到,表中的行之间是有指针相连的,即数据页中的每个记录除了存放数据,还会包含一个指针,指向其下一行记录。各记录形成一种链表结构。当然,这种结构并不是所有数据库系统都会采用的。


索引怎样提高性能

考虑这样一种情况:如上图,银行数据库的account表有编号(ID),城市(City)和余额(Balance)三列。表中一共有10万行数据。现在要列出属于Mianus这个城市的所有账号,查询语句为:

Select * From account Where city=‘Mianus’

为了找出满足条件的查询,数据库管理器必须扫描account表中的所有行,逐行匹配,即表扫描。这会向缓冲池调入大量的数据页,执行大量I/O操作无疑是非常影响性能的。

如果在city列建立索引,则DB2查询优化器会在索引中扫描匹配的行,然后根据该行的逻辑指针找到那些满足条件的表数据行并将对应的数据页调入缓冲池,从而大大减少I/O操作。【一般而言,索引是可以常驻缓冲池的,所以对索引的扫描可以无需进行耗时的I/O操作】

当然上面的索引工作机制的描述是直观性的,真正的索引工作机制下文再讨论。

索引的分类–按结构分

索引按照结构可以分为有序索引(ordered index)和散列索引(hash index)两种基本类型。其中有序索引是基于值的顺序排序,根据值的排序进行索引值的查找。而散列索引则是基于将值平均分布到若干散列桶(hash bucket)。根据散列函数确定索引值所在的散列桶。

有序索引

顺序文件索引

有序索引的一种最简单实现形式是顺序文件索引。顺序文件索引结构更加类似一张两列表,所有的索引值顺序排列,进行查询的时候逐行扫描索引中的各行记录,找到匹配项后就能根据逻辑指针找到表数据行的数据页。

那么,是不是建立索引的列的所有列值都必须成为索引中的索引值呢?不是。

稠密索引(dense index)和稀疏索引(sparse index)

我们将表中所有列值建立一个索引记录的索引称为稠密索引(dense index),将只为某些列值建立索引记录的索引称为稀疏索引(sparse index),如图:


                                                稠密索引                                                                                                         稀疏索引

左侧的稠密索引很好理解,右侧的稀疏索引是怎样工作的呢?该索引只为Brighton、Mianus,和Redwood建立的索引记录,当需要查找Downtown时,由于顺序上Downtown在Brighton和Mianus之间,所以就根据Brighton这条记录的指针找到Brighton的数据页,从Brighton这一行记录开始根据记录的指针逐个查找,直到找到全部Downtown的行记录为止。

很显然,对于稀疏索引,数据行在数据页中必须按照索引记录的顺序而顺序排列才可能有效,否则有的列值就可能找不到或者找不全。但是和稠密索引相比,稀疏索引有着节省存储空间的优势。

多级索引

有时候,即便使用稀疏索引,由于数据量大且索引列上的列值多,索引本身也会变得非常大而难于有效处理(索引过大就难以保证常驻内存,进行磁盘读取的话,索引越大,需要的I/O越多),为了处理这种问题,我们使用了多级索引技术,其思想就是对索引建立索引。以一个二级索引为例,先根据外层索引定位到内层索引相应位置,在根据内层索引定位到表数据的数据页。这样的多级索引结构肯定会使得外层索引中的索引记录会少很多,如何便可以只将外层索引常驻内存从而达到减少I/O的目的了。

当然,无论是哪一级索引,都既可以是稠密索引也可以是稀疏索引(最内层可能只能是稠密索引)。实际上,索引记录本身就是顺序存储的,所以建立在索引上的索引通常是稀疏索引,这样才能更好的发挥多级索引的作用。


B+树索引

顺序文件索引的最大缺点在于,随着表数据行的增大和索引的增大,索引查找性能(多级索引的复杂度,索引扫描量)和数据顺序扫描性能(数据在增删改等操作中会变得非常混乱,难以维护)都会下降。虽然这种性能下降可以通过表重组和索引重组解决,但是频繁的重组同样是我们不愿意看到的。

因此,一种新的索引结构被广泛接受,这就是B+树索引。B+树是B树(平衡查找树,一种多路查找树)的一个重要变种(参考:B 树、B- 树、B+ 树和B* 树),B+树索引结构是使用最广泛,在数据插入和删除的情况下仍能保持其执行效率的几种索引结构之一。目前DB2的索引结构就是B+树索引,Oracle的普通索引结构是B+树索引的变种B*树索引。

B+树索引采用平衡树(balanced tree)结构,其中根结点到每个叶结点的路径长度都是相同的(所有叶结点都在同一层),树中除根结点外,每个非叶结点有[n/2] (这里的[]符号表示取天棚,如[3/2]=2。天棚符号显示不出。下同)到n个子结点,每个页结点有[(n-1)/2]到n-1个索引值(key-value,我们称为搜索码:search key)。至于n是什么,后面会解释。一个B+树的例子:其中n=4,索引值(搜索码)是2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.



B+树索引结构

既然DB2的索引是B+树索引,那么B+树索引在磁盘上到底是怎样存储的呢?

前面介绍过,索引和表数据行一样,存储在数据页中。事实上,一个索引数据页就是索引B+树的一个结点!

每个结点在数据页中的存储方式是这样的:


其中P1,P2,…….,Pn是n个指针;K1,K2,……,Kn-1是n-1个搜索码(索引值),这n-1个搜索码是按照从小到大的顺序排列的。

对于非叶结点:

P1指向另一个结点数据页,这个结点数据页中的所有搜索码值都小于K1(按某种排序规则规定的大于小于关系,比如Brighton<Downtown);

P2指向另一个结点数据页,这个结点数据页中的所有搜索码值都大于或等于K1且都小于K2;

依此类推,Pn指向的结点数据页中所有搜索码值都大于或等于Kn-1。

而对于叶结点:

P1就是K1搜索码所对应的表数据行的逻辑指针,直接指向数据行的地址(页号+槽号);

同理,P2指向K2搜索码数对应的表数据行的逻辑指针,……,Pn-1指向Kn-1搜索码数对应的表数据行的逻辑指针;

最后的Pn指针则指向该B+树中的下一个页结点。


B+树索引分析

我们认为一个(指针,搜索码)对,即一个(P,K)对是一个索引项(index entry,一个索引项就是索引数据页中的一条记录)。假设一个B+树索引的一个索引项大小为40B,一个数据页中可以存储的索引项数大致是4KB/40B=100个。那么,n=100。这就是B+树索引中的n的来历。它完全是由索引数据页大小和索引项大小决定的。(当然,这个例子中按计算值来说,n应该等于101,这样才是100个搜索码,101个指针,才有100个索引项。但是由于页面空间利用和方便计算的原因,直接取个大概值100)

按照树结构的层数公式:层数= (K表示总共的搜索码数量,m表示每个结点的子结点数)。由于非叶结点的子结点数为[n/2]到n-1,那么如果所有非叶结点的子结点都是[n/2]个,B+树索引的层数为;如果所有非叶结点的子结点都是n-1个,索引B+树的层数则为。也就是说,B+树索引的层数最多为层。由于B+树根结点到所有叶结点的路径都一样长,而且所有搜索码都在叶结点上,所以,查找任意一个搜索码所需要的路径长度都是一样的。

继续假设一个表中建立了索引的列上有100万个不同的列值,即有100万个搜索码(索引值),则B+树索引的层数最高为层。可见,通常DB2B+树索引的层数不会超过3层。(100万个不同的搜索码才4层,很少需要在这样的列上建立索引。除非是主键。主键默认是有唯一性索引的)层数越低表示查找到所需的搜索码越快,定位相应的数据行的物理位置越快。

下面以n=3为例看看上面account表的city列的索引的结构是怎样的:


B+树索引生成

下面的图详细演示了一棵n=5的B+树索引的生成过程(叶结点之间的指针未标出):


关于B+树的生成规则以及结点中搜索码的添加,删除和结点的合并分裂规则这里不作介绍,有空再写。

从B+树的结构和相关规则可以看出,B+树在插入和删除操作方面会相对复杂,不能会带来性能开销,还会增加空间开销。但是由于数据库中数据的查询操作通常是远多于删除和插入操作的,也就是说,B+树索引带来的稳定高性能查询优势是其他索引结构无法比拟的。插入和删除带来的开销实际上也是可以接受的,因为它减小了表重组和索引重组的代价。此外,由于结点有可能是半空的,这会造成空间的浪费。但是这种浪费依然是可接受的。

多值指针

还有一个问题在之前的讨论中一直被回避着,那就是,如果一个索引值(搜索码)对应着表中多个数据行(这种情况是极为普遍的,比如上面account表中的Perryridge),那么,该叶结点的指针该指向谁呢?

如果是顺序文件索引,可以通过指向第一个满足条件的行,再根据各行的next指针来遍历所有满足条件的行(这一点上文有解释)。可是B+树索引并没有这样的行间next指针结构。

包括Oracle数据库在内的大多数数据库产品采用的策略是使用散列桶(hash bucket)。即对于一个搜索码对应多个数据行的情况,其叶结点指针指向一个散列桶,再通过遍历散列桶来获取所有满足条件的行地址。(这个策略类似B树索引结构)

而DB2则是利用其优秀的索引压缩技术而采用了一种新的解决方案,DB2使用一种逻辑块结构来解决搜索码值重复的问题,如图:


一个逻辑块包含一个前缀(Prefix,大小为2B),一个搜索码(Keyval)和一个与该搜索码对应的RID(大小为4B)列表。规定一个逻辑块中的搜索码后跟的RID的个数最多为255个。假设搜索码A有N个不同的数据行与之对应,则意味着一个搜索码对应N个RID。如果N<=255,则一个逻辑块中能够包含该搜索码以及其全部RID。如果N>255,则需要另外生成一个逻辑块,该逻辑块中的搜索码仍然是之前的搜索码A,RID列表中为剩下的RID。如果仍然无法容纳剩余的全部RID,则继续生成该搜索码的逻辑块,直到能够全部容纳为止。多个逻辑块则以前缀Prx来进行区分(前缀不仅能区分同一搜索码的不同逻辑块,还能区分不同搜索码的逻辑块)。如此,一个逻辑块类似于一个索引项。但是这里的索引项跟上面无重复搜索码的索引项是有着本质的区别的。

找到一篇详细介绍DB2索引压缩技术的论文,有时间再翻一翻:

http://www2.hawaii.edu/~lipyeow/pub/vldb09-indexcompression.pdf (很值得研究的一篇论文)


散列索引

有序索引的一个缺点是必须访问索引结构来定位数据,或者必须使用多路查找,这些都导致相对过多的I/O操作。而基于散列(hashing)技术的索引则能够避免访问索引结构。介绍散列索引前先理解一下散列的相关概念。

静态散列

散列技术中有一个重要的概念,那就是桶(bucket)。桶表示能够存储一条或多条记录的存储单位。通常一个桶就是一个磁盘块,但也可能大小不定。我们用K表示所有搜索码的集合,用B表示所有桶的集合。散列技术的思想就是:将所有的搜索码K及其相关信息按照某种规则(称这种规则为散列函数h)分散到各个散列桶中(就是一种映射关系)。当查找某个搜索码时,就可以根据规则计算出该搜索码所在的桶,然后在桶中找到搜索码及其信息。这种方法可以在一开始就定位到小范围内进行查找工作,效率可想而知是很高的。

散列函数

散列技术所要解决的首要问题就是散列函数的确定了。不好的散列函数可能导致所有搜索码只被分配到单独几个散列桶中,这既导致散列桶空间的浪费,也使得散列查找的优势丧失(不得不在一个桶中查找大量记录)。良好的散列函数至少需要满足两大特性:分布是均匀的;分布是随机的。散列函数的确定是非常灵活的,可以非常简单(比如简单求余,根据余数的不同将搜索码分配到不同桶中),也可以异常复杂。不作过多讨论。

桶溢出

当插入一条记录,而根据散列函数映射到的散列桶已经没有存储空间存放该记录的搜索码,就会发生桶溢出(bucket overflow)。发生桶溢出的可能原因有:

1.桶不足(Insufficient bucket)。即桶的总数不够,当然这种问题一定程度上是由于散列函数的不合理造成的,它导致大量的搜索码通过散列函数只能映射到少数几个桶中。当然这也是无法完全避免的,任何散列函数都只能将搜索码映射到有限的桶中,任何桶的存储空间也是有限的。但是搜索码的数量可以是无限的。

2.偏斜(Skew)。即大量的搜索码分布到少数几个桶中,其他的桶中的记录很少或者没有。这种情况一方面也是由于散列函数选取不当,另一方面也可能是特定的搜索码集合本身具有一定的耦合性(比如多个记录具有相同的搜索码)。

解决这一问题的策略就是使用溢出桶(overflow bucket)。即如果一个搜索码映射到的桶已经满了,则为这个桶增加一个溢出桶,将这个搜索码存储在溢出桶中。如果溢出桶也满了,就再增加一个溢出桶,如此反复。散列桶和它的溢出桶通过链表连接起来,称为溢出链(overflow chaining)。


很显然,一个散列桶上挂的溢出桶越多,散列桶所拥有的优势也就丧失越多,因为不得不进行更多的查找操作。

以上的散列技术应用与索引就产生了散列索引了。

散列索引将搜索码及其相应的逻辑指针封装成一个散列结构,将散列函数作用于搜索码,将这些散列结构分配到不同的散列桶中。当进行查找时,根据搜索码找到装有含该搜索码的散列结构的散列桶,然后在散列桶中更加搜索码找到对应的散列结构,得到散列结构中的逻辑指针就能找到对应的表数据的数据页及槽地址了。

以一个桶能够存储2个封装了搜索码和逻辑指针的散列结构为例(以ID主码为搜索码):


以上就是使用静态散列技术构造散列索引的方法了。

动态散列

静态散列索引的一个主要的缺陷是,随着散列函数的确定,桶地址集合B也就确定了。(比如将散列函数定义为对10求余,则散列桶就只有10个:0-9)。随着数据库的不断增大,就需要使用溢出桶处理溢出问题了,但过多的溢出桶会导致效率的明显下降。

一种处理方法是一开始就确定一个能使用足够多散列桶的散列函数,但这必然造成前期存储空间的巨大浪费。另一种方法是周期性的对散列结构进行重组。重新选择散列函数,重新分配桶,但这无疑是一个复杂而耗时的工作。

为了克服静态散列的缺陷,一些动态散列(dynamic hashing)技术被提出并应用与散列索引,以保证数据库的增大不会给性能带来大的影响。一种比较好的动态散列技术是可扩充散列(extendable hashing),当数据库增大或缩小时,通过桶的分裂或合并来适应数据库大小的变化。具体实现就不解释了。

索引的分类–按功能分

除了按照结构将索引分为有序索引和散列索引外,还可以按照索引功能将其分为唯一索引,非唯一索引,集群索引,非集群索引和MDC块索引这样的5种类型。

唯一索引(unique index)和非唯一索引(nonunique index)

实际上,索引的优势主要体现在两方面:提高查询效率和保证数据唯一性。其中保证数据唯一性的优势就是依靠唯一索引提供的。

唯一索引是指对某一列创建的索引必须保证每一个key-value(索引值,搜索码)只能对应一个Row-pointer。比如最开始的示意图中,一个Downtown的key-value就对应了两个表数据行的指针;一个Perryridge的key-value对应了3个表数据行的指针。这样的索引就是非唯一索引。

那么要保证索引是唯一索引,显然就必须保证对应表中的建立了索引的列上没有两行的列值是相同的。也就是说,唯一索引效果上等同于非唯一索引+索引列唯一性约束。

只有在表中某列上的所有列值都不相同是才能在该列上成功建立唯一索引。一旦在表中某列上建立了唯一索引,那么向表中插入的任何数据行都不允许在该索引列上出现重复值,否则插入失败。需要注意的是:创建了唯一索引的列上的数据允许为空,但是一旦有数据,就必须是唯一的。

对于任何一张表,一旦指定了主键,那么数据库会默认在主键上创建一个唯一索引,有时称主键上的唯一索引为主键索引,主键索引其实就是在唯一索引和非空约束的组合实现(主键是不允许为空的)。另外,一旦为某个列建立了唯一性约束,数据库同样会默认在该列上创建一个唯一索引。

集群索引(clustered index)和非集群索引(nonclustered index)

概念

集群索引又称聚集索引,聚簇索引,其中聚簇索引是各数据库通用的常用的叫法,集群索引是DB2官方叫法。同时聚簇索引又称主索引(primary index)【注意:主索引并不表示该索引是建立在主键上的,事实上,主索引通常建立在非主键上】。聚簇索引的概念对于有序索引和散列索引都是有效的,但是对于有序索引才有意义。通常散列索引都是非聚簇索引。(当然散列聚簇索引也是存在的)

我们知道,无论是顺序文件索引还是B树、B+树、B*树索引,这些有序索引中索引值(搜索码)都是有一定的排列顺序的。如果这些索引值(搜索码)对应的数据行在数据页存储空间中跟索引值的排列顺序是一致的,那么这样的索引就是聚簇索引。反之就是非聚簇索引(nonclustered index,非聚簇索引又称辅助索引:secondary index)。注意:这里只要求排列的顺序一致,并不要求索引值在索引数据页上是连续的,也不要求表数据行在常规数据页上是连续的。如图是DB2聚簇索引和非聚簇索引的示例:


很显然,由于聚簇索引要求数据页中的数据行顺序上与索引值的顺序保持一致,而数据行的排列顺序是一种物理上的顺序,不可能要求数据在磁盘上同时满足多种物理排序(就像不可能要求一群人人既按身高排队的同时又按照年龄排队一样),所以,一个表上只允许有一个聚簇索引。对于非聚簇索引则没有限制。

联系前面提到的稀疏索引和稠密索引的含义,可以知道,非聚簇索引必须是稠密索引,因为如果是稀疏索引,那么由于索引值与数据行排序的不一致,无法定位没有出现在索引值中的搜索码。

聚簇索引的优势

那么,既然聚簇索引有这么大的限制,聚簇索引存在的必要性在哪呢?

聚簇索引相较非聚簇索引唯一的优势是拥有更高的查询性能。参照上图,试想account表上的这样一条查询语句:

select * from account where balance > 500

如果在balance列上建立了非聚簇索引,那么,balance > 500的行可能分布在各个数据页上,那么要查询到满足条件的所有行,就必须将大量的数据页调入缓冲池中(每一页上只有少数几行是满足要求的),而且,数据库的预取机制的效率就显得不怎么高。不仅如此,由于包含满足条件的行的数据页分散分布,数据在磁盘上很可能也分散到距离间隔比较大的扇区上。因此,这样的查询不仅I/O操作多而且I/O也更费时。

如果在balance列上建立的是聚簇索引,那么balance>500的行很可能就分布在一个数据页内或者一个数据页中有大量满足条件的数据行,需要调入缓冲池的数据页就会少很多,预取机制也能较好的发挥作用。同时,数据在磁盘上也会分布在邻近的扇区。因此,这样的查询不仅I/O操作少 而且I/O相对省时。

聚簇率(clustering ratio)

使用聚簇索引固然有查询方面的优势,但是在数据插入方面就产生一个问题:新插入的数据应该放在哪个数据页的什么位置?由于聚簇索引要求数据行与索引值顺序保持一致,那新插入的数据行以及其索引值是否必须寻找相应位置执行插入操作呢?如果数据页中相应位置没有足够的空间插入该怎么办呢?可以想象,如果要保证顺序的严格一致,必然会导致大量的数据迁移,这样的花销是不可接受的。所以,真正的处理办法是允许有一定的顺序不一致出现,即便有些数据是无序的,仍然认为该索引是聚簇索引。

我们把索引中满足聚簇顺序条件的(索引值,数据行)对占该索引上所有(索引值,数据行)对的比例称为聚簇率,聚簇索引中85%以上的聚簇率是可接受的。否则就需要进行重组。

顺便提一个小技巧:

假设已经建好一张表,准备向表中导入大量数据,且要在某列上建立索引,那么:

如果是建立非聚簇索引,最好是先导入数据,然后建立索引。因为这样保证B+树索引建立时已经存在大量搜索码,无需在B+树生成后进行频繁的插入,合并,分裂操作。

如果是建立聚簇索引,最好先建立索引,然后导入数据。因为如果先导入了数据,再建索引,就必须对已经存在的数据进行耗时的重新排序。

聚簇索引的实现

还有一点需要说明,那就是,虽然各种数据库产品都有聚簇索引的概念,但具体的实现方式和索引结构也是有区别的。DB2的聚簇索引结构如上图所示,聚簇索引的叶结点和非聚簇索引一样,都是指向相应数据页的逻辑指针。即索引数据页和常规数据页是严格分开的。但是包括Oracle,SQL Server在内的大部分数据库的聚簇索引的页结点不是指向数据页的指针,而是页结点本身就是数据页。也就是说,索引数据页和常规数据页发生了融合,二者已经没有了严格的界限。如图(这是SQL Server数据库的聚簇索引和非聚簇索引的对比图,SQL Server数据库的索引是二叉树结构):


MDC块索引(MDC block index)

MDC块索引与多维集群表相关,还没有研究过。

标准表的表、索引和数据页的关系

标准表是相对与多维集群表而言的,常规表就是标准表。其实标准表,索引和数据页的关系在这篇文章和《数据库学习笔记—-磁盘存储内部结构》这两篇文章里已经解释得很清楚了,这里放上一张全景的关系结构图:


DB2索引优化

索引虽然能够大大提升查询效率,但是并不是对所有查询都适用的。比如对于“Select * From account where balance != 500”这样的语句,balance列上的索引基本上是无效的。(这是很好理解的,“不等于”在B+树索引中怎么能查找呢?)

我们把查询语句中Where后面的表达式称为谓词。DB2中谓词能否使用索引的情况列表如下:

深入理解数据库磁盘存储(Disk Storage)

数据库管理系统将数据存储在磁盘、磁带以及其他的裸设备上,虽然这些设备的访问速度相比内存慢很多,但其非易失性和大容量的特点使他们成为数据存储的不二之选。

本文主要讨论大型数据库产品的磁盘存储内部结构,这对于深入理解数据库各种数据结构具有至关重要的作用。

数据库磁盘存储的体系结构


以上两图分别展示了存储器分级结构以及磁盘内部物理结构,不是本文重点,不赘述。需要强调的是:一次完整的输入输出(IO)操作的时间=磁盘轴旋转时间(旋转延迟)+磁盘臂移动时间(寻道时间)+数据传输时间。三者所需时间的平均经验值为:0.004秒、0.008秒和0.0005秒。所以,一次完整的IO时间的经验值是0.0125秒,即1/80秒。

对于大型数据库而言,即便是这极短暂的0.0125秒,频繁的IO操作会将这微不足道的时间累积得非常可观,因此磁盘存储的优化对于数据库效率的提升是非常必要和重要的。不同的数据库产品的磁盘存储内部实现是不同的,本文只讨论Oracle、DB2大型数据库产品,二者细节上虽有不同,但结构大体上是一样的。

Oracle和DB2数据库的存储模型如图:


可以看出,数据库中的数据都存储在表空间中。表空间即是管理将逻辑数据库设计映射到操作系统物理存储中的一个数据库对象,用于指明数据的物理位置。关于表空间,以后再讨论。

Oracle数据库磁盘存储的逻辑结构为:一个数据库(Database)对应多个表空间(Tablespace),一个表空间对应多个段(Segment),一个段对应多个区(Extent),一个区对应多个数据块(Data Block),真正的数据就保存在数据块中。这里有以下几点需要说明:

1.Oracle中一个数据块的大小默认是2KB(支持2KB,4KB,8KB,16KB,32KB),而DB2中则默认是4KB(支持4KB,8KB,16KB,32KB);

2.Oracle中有段(Segment)的概念,而DB2中没有这一概念,表空间直接是各个容器(数据文件)中的区(Extent)组成,不过也还是有一个很弱化的Extent组概念。下面提到的关于Segment的内容则全部是针对Oracle的;

3.Oracle中的数据块称为Oracle Block,而DB2中则直接称为Data Page(数据页)。

4.Oracle中的Extent称为区,而DB2中则称为扩展数据块。为方便阅读,本文中统称为区。

                                 Oracle磁盘存储逻辑结构


  

                                           DB2磁盘存储逻辑结构

要注意:这里的表空间,段,区,数据块(页)全部都是数据库中的逻辑概念,并不是物理存在的,那么数据库磁盘存储的逻辑结构如何映射到操作系统磁盘存储的物理结构中呢?

先来看看表空间的物理映射。表空间在操作系统上是由容器(Container)承载的,对于系统管理表空间(SMS)【注意:Oracle不存在系统管理表空间,其表空间全部都是数据库管理的】,其唯一的容器是文件目录;而对于数据库管理表空间,其容器则是文件或者裸设备(比如磁带、磁盘柜)。这里我们不讨论系统管理表空间,只关注数据库管理表空间下的数据库磁盘存储。由于数据库对于文件和裸设备这两种容器操作上是同等对待的,所以以文件容器为例进行讨论。文件容器本身是一个由DMS表空间使用的预分配大小的文件,一个表空间可以有多个文件容器,即有多个数据文件。也就是说:一个逻辑上的表空间映射为多个物理上的数据文件。

再来讨论数据块(页)的物理映射。我们知道,物理结构上,操作系统中的文件是由多个操作系统的块(Block)组成的(Linux,Unix系统的块大小为512B,而Windows系统的块大小为1KB),而上面说了,数据库中的数据是以数据块(页)为单位存放的,,那么数据库中的数据块(页)和操作系统的块是什么关系呢?事实上,若干个操作系统块组成一个数据库的数据块(页)。对应区(extent)和段(segment)的映射并没有物理单位与之对应,而是在一个数据文件中会包含多个段,每个段里又包含多个区(每个段中的区的个数不一定是一样的;DB2中数据文件中直接以区为单位,没有段的概念),每个区包含若干数据块(每个区中数据块的数量也不一定一样)。另外,和表空间一样,段也是可以跨文件的,即一个段可以由不同文件中的区所组成。

数据库磁盘存储的逻辑/物理映射图解如下(DB2中没有Segment这一层):


关于这些逻辑单位的具体讨论以后再说。现在只需要了解大体的体系结构。通过上面的介绍可以看到,数据库管理的表空间自成一体,具有平台无关性,俨然是一个小型的独立文件系统了。

数据库磁盘存储的内部实现

了解了磁盘存储的体系结构,再来看一看数据库系统中,数据具体是如何进行存储的。

当创建一张表(Table)的时候,会为其指定表空间,一旦表成功创建,数据库系统就要为表提供磁盘空间。

Oracle数据库会自动为一张表分配一个Segment(段),这个Segment称为Data Segment(数据段)【注:一张表只能被分配一个数据段。Oracle一共有四种类型的段,分别是Data Segment(数据段),Index Segment(索引段),Rollback Segment(回滚段)和Temp Segment(临时段)】。当为表分配的数据段全部写满的时候,数据库管理系统会为这个数据段增加新的区(Extent),也就是说,数据段空间分配完后并不是需要多少空间就为段增加多少空间,也不是直接在区中增加数据块,而是一次性增加一个Extent(这样做避免了频繁的Segment扩容),Extent是空间分配的最小单位,而且Extent在表空间中的各个容器上是均衡分配的。另外,数据块(页)是最小的存储单位,也即最小的I/O单位,所有数据都是按块(页)存储,读出的时候也是直接将整个数据块(页)读入内存中的。至于DB2,其方案与Oracle基本相同,所不同的是没有Segment分配的问题。

我们以DB2为例,看看数据存储具体是怎样的。【参考牛新庄:深入解析DB2】

一个DMS表空间可以有多个容器(文件或裸设备),DB2将Extent均衡的写到各个容器上。即当需要请求一个Extent时,数据库管理器这个Extent分配到下一个容器上。这种方案保证了各容器的均衡利用,提高了并行访问效率。如左图:

                                         表空间容器均衡写


                      表空间容器,Extent,数据页和表空间之间的关系


新建一个称为HUMANRES的DMS表空间,其Extent大小为2个Page(即数据块),每个Page大小为4KB。表空间有4个容器,每个容器内有少量已分配的Extent:表空间中DEPARTMENT和EMPLOYEE表中都占用了7个Page,按照上面介绍的分配规则,这两个表中的数据都会写到四个不同的容器中(7个Page需要分配4个Extent,每个Extent依次分配到各个容器中),另外,一个Extent只能由一个表所写,即便表数据不能完全利用Extent中的空间,Extent中的空闲空间也只能空着,不能继续写入其他表中的数据(这是由Extent是空间最小分配单位决定的)。如右图。

数据块(页)存储

下面进一步深入,分析一下数据库磁盘存储最小单元数据块(Data Block or Data Page)内的具体结构是怎样的。对于Oracle和DB2,二者的数据块结构是不同的。以下分别讨论。至于其他的数据库产品,不在讨论之列。

Oracle数据库的数据块(Data Block)结构及相关特性

(参照:http://docs.oracle.com/cd/B28359_01/server.111/b28318/logical.htm

数据块格式

Oracle 数据块的格式无论是表、索引还是cluster 数据,格式都是很类似的,如图:


公共和变量块头( Common and Variable Header)

头部包含了通用块信息,例如块的地址和段的类型 ( 例如表或者索引 )

表目录(Table Directory)

这部分信息包含了在这个块中该表或该索引的相关信息。

行目录(Row Directory)

这部分包含了数据块中的实际行的信息 ( 包括行数据区域中每行的地址 ) ,一旦数据块头部的这个行目录的空间被分配了,那么即使该行删除了,这段空间仍然不能回收。

因此一个当前为空的数据块,此区域包含数据块中存储的数据行的信息(每个数据行片断( row piece ) 在行数据区( row data area )中的地址)。 [ 一个数据块中可能保存一个完整的数据行,也可能只保存数据行的一部分 ,所以文中使用 row piece] 。只有在数据块中插入( insert )新数据时,行目录区空间才会被重新利用。

头部信息区(Overhead )

块头( header/Common and Variable ),表目录( Table Directory ),行目录( Row Directory )这三部分合称为头部信息区( Overhead )。头部信息区不存放数据,它存放的整个块的信息。头部信息区的大小是可变的。一般来说,头部信息区的大小介于 84 字节( bytes )到 107 字节( bytes )之间。

可用空间(Free Space)

可用空间是一个块中未使用的区域,这片区域用于新行的插入和已经存在的行的更新。可用空间也包含事务条目,当每一次 insert 、 update 、 delete 、 select ..for update 语句访问块中一行或多行数据,将会请求一条事务条目,事务条目的请求空间与操作系统相关,在多数操作系统中大约所需 23 个字节。

行数据(Row Data)

这部数据块包含了表或索引的数据,行也可能跨数据块,这也就是行迁移现象。


可用空间管理(Free Space Management)

可用空间可能是自动或人工管理。

可用空间是由 Oracle 内部的段自动管理的,段内的可用 / 已用空间用位图来跟踪。自动段空间管理提供了以下好处:

l  使用便捷

l  更好的空间利用率,特别是那些行大小变化很大的对象

l  并发访问的动态调整

l  性能 / 空间的平衡

数据块可用空间的利用和压缩

Delete 和 update( 把原值变小 ) 可增加数据块的可用空间。在以下情况下 insert 语句才能有效地利用已释放的空间。

假如 insert 语句在同一个事务中,而 insert 前面的语句刚好释放了相应的空间,这时候 insert 语句可以利用该空间

假如 insert 语句与释放空间的语句不在同一个事务中,那么只有当其他事务提交后并且刚好需要空间的时候, insert 语句才能利用该空间。

释放的空间也可能不是连续的,只有当 以下两个条件都满足的时候, Oracle 才会合并和压缩数据块的可用空间。

1 一个 insert 或 update 语句试图使用足够空间创建新行的时候;

2 自由空间是分散的以至于不能插入毗邻空间的时候;

这就是所谓的“块重组(Block Reorganization)”。事实上,Oracle和DB2在对待碎片空间上的策略是一致的,即:行数据被删除后,该空间空置,当块空间不足时进行重组。而其他数据库的策略是行数据删除后,其他行数据顺移以保证可用空间是连续的。显然,这种做法影响数据库效率。

 

行链接和行迁移(Row Chaining and Migrating )

行链接( Row Chaining ):如果我们往数据库中插入( INSERT )一行数据,这行数据很大,以至于一个数据块存不下一整行, Oracle 就会把一行数据分作几段存在几个数据块中,这个过程叫行链接( Row Chaining )。

如果一行数据是普通行,这行数据能够存放在一个数据块中;如果一行数据是链接行,这行数据存放在多个数据块中。

行链接又称为行跨页,Oracle允许行跨页,但DB2是不允许的。


行迁移 (Row Migrating) :数据块中存在一条记录,用户执行 UPDATE 更新这条记录,这个 UPDATE 操作使这条记录变长,这时候, Oracle 在这个数据块中进行查找,但是找不到能够容纳下这条记录的空间,无奈之下, Oracle 只能把整行数据移到一个新的数据块。原来的数据块中保留一个“指针”,这个“ 指针”指向新的数据块。被移动的这条记录的 ROWID 保持不变。

 


PCTFREE和PCTUSED

PCTFREE 参数用于指定块中必须保留的最小空闲空间百分例。之所以要预留这样的空间,是因为 UPDATE 时,需要这些空间。如果 UPDATE 时,没有空余空间, Oracle 就会分配一个新的块,这会产生行迁移( Row Migrating ),进行空间预留能够一定程度上保证数据库访问效率。

PCTUSED 也是用于设置一个百分比,当块中已使用的空间的比例小于这个百分比的时候,这个块才被标识为有效状态。只有有效的块才被允许插入数据。

PCTFREE和PCTUSED作用示意图如下:

DB2数据库的数据页(Data Page)结构及相关特性

(参照:http://pic.dhe.ibm.com/infocenter/db2luw/v9r7/index.jsp?topic=%2Fcom.ibm.db2.luw.admin.perf.doc%2Fdoc%2Fc0007337.html

数据页格式

在标准表中,数据在逻辑上按数据页的列表进行组织。这些数据页根据表空间的Extent大小在逻辑上分组到一起。这个Extent组类似于Oracle中的Segment,但Extent组没有Segment那样的强制概念。

每个数据页都具有相同的格式。每一页的最前面都是页头,后面跟着槽(Slot)目录,然后是可用空间和记录。

页头(Header)

用于存放BPS HEADER和一些页的信息字段,其中BPS HEADER占48字节,整个页头大概占91个字节。

槽目录(Slot Directory)

槽目录类似Oracle的数据块中的行目录,槽目录中的每个条目都与该页中的一个记录相对应。槽目录中的条目代表记录开始位置在数据页中的字节偏移。值为 -1 的条目与已删除的记录相对应。

可用空间(Free Space)

DB2可用空间严格来说包括通常意义上的常规可用空间和嵌入的可用空间。其中常规可用空间可用直接存储数据,而嵌入的可用空间通常是记录被删除后产生的碎片空间,不能直接使用,只有当页重组后合并到常规可用空间后才能被使用,这一点和Oracle类似。

记录(Record)

已经存储了数据的空间,类似于Oracle中的行数据。即表中的行存放于页面中成为记录。根据数据页大小以及记录大小的不同,每个数据页中包含的记录数(即行数据数)也会有所变化。大多数页仅包含用户记录(即普通的数据库数据)。但是,少数页包含由数据服务器用于管理表的特殊内部记录。例如,在标准表中,每 500 个数据页就有一个可用空间控制记录(FSCR)。这些记录用于映射后续每 500 个数据页(直到下一个 FSCR 为止)中可供新记录使用的可用空间。另外,在DB2 V9之前,每个数据页最多可以存放255条记录,而DB2 V9之后,每个数据页理论上可以存放65000条记录(与RID有关,暂不讨论),但实际上受限于数据页大小,每个数据页大概能存放2300多条记录。

行链接和行迁移

DB2是不允许行(记录)跨页的,即不允许行链接。但是允许行迁移(DB2中又称为行溢出),

当表中存在变长数据类型时,容易发生行溢出现象,行溢出有时也叫行迁移,它表示当我们更新变长数据类型的字段时,由于更新的数据长度比原数据长,以至于当前的数据页无法存放整行数据时,就需要把这行数据存放到一个新的数据页,并在原来的数据页内存放该行新位置的指针以指向新行位置,被移动的数据的RID(RID以后讨论)保持不变。显然,如果大规模出现行迁移的现象,那么必然会对数据库访问的效率产生严重影响(I/O大幅增加),如果表中发现大量行迁移现象,建议进行重组(REORG)操作,重新规划数据存储位置消除行溢出。



对应DB2数据页还需要强调的一点是:DB2的数据页和Oracle数据块一样,也有PCTFREE和PCTUSED的概念,其含义与作用也大致相同,不赘述。


另外可以看到,Oracle的数据块结构和DB2的数据页结构是非常相似的。还有一点,二者的行数据都是从高位开始向低位写,而行目录则是由低位向高位写,为什么要这样呢?因为数据的插入是一个两头写的过程,既要将数据写入到可用空间中成为行数据或记录,又要更新头部后面的行目录或槽目录,如果同侧写不利于空间的扩展。下图是一个直观图:



数据行结构

现在对数据块(页)的具体结构已经有了一个大概的了解,那么表中的一行数据是怎样以行数据(记录)的形式保存在数据块(页)中的呢?这个问题看似简单,实际上,一个数据行(记录,即上图中的Row)的结构是非常复杂的,这里以DB2中数据行的结构为例。如图:


各参数解释如下:


可以看到,当元组(即表中的行)中存在变长列的时候,不管该列位于什么位置,在数据行(记录)中都被挪到最后面存储,而定长列则顺序存储。

【注:表的属性列在定义的时候指定了数据类型,有的数据类型是变长的,比如varchar,其大小随实际值的变化而变化,有的列数据类型的定长的,比如int为32位,物理该列上的实际值是多少,都占用4个字节。一旦列中出现变长数据类型的列,则该元组为变长元组。】

下图是状态位A的每一位的含义(1个字节=8位),状态位B是未使用的。


下面看看一个定长的元组(行)在数据行(记录)中具体是如何存放的:


有些复杂,将此图与前面贴的结构图对照着看。【注意:所有数据在数据页的数据行(记录)中都是以十六进制存放的,且为逆序存放

下面是变长的元组(行)在数据行(记录)中具体存放方式,与定长元组的存放方式大同小异:


对于含大对象数据类型的元组,其大对象数据并不与数据行存放在一起,而是与数据行分开放置于数据库的不同页中,在该元组(行)的数据行中存放一个指向该大对象的指针。如图:

B 树、B- 树、B+ 树和B* 树

B

即二叉搜索树:
1. 所有非叶子结点至多拥有两个儿子(LeftRight);
2. 所有结点存储一个关键字;
3. 非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;
如:


B树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;
如果B树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变B树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;
如:


B树在经过多次插入与删除后,有可能导致不同的结构:


右边也是一个B树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的树结构索引;所以,使用B树还要考虑尽可能让B树保持左图的结构,和避免右图的结构,也就是所谓的平衡问题;
实际使用的B树都是在原B树的基础上加上平衡算法,即平衡二叉树;如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法是一种在B树中插入和删除结点的策略;

B-

是一种多路搜索树(并不是二叉的):
1. 定义任意非叶子结点最多只有M个儿子;且M>2
2. 根结点的儿子数为[2, M]
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]
4. 每个结点存放至少M/2-1(取上整)和至多M-1个关键字(至少2个关键字);
5. 非叶子结点的关键字个数=指向儿子的指针个数-1
6. 非叶子结点的关键字:K[1], K[2], , K[M-1];且K[i] < K[i+1]
7. 非叶子结点的指针:P[1], P[2], , P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
8. 所有叶子结点位于同一层;
如(M=3):


B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;
B-树的特性:
1. 关键字集合分布在整颗树中;
2. 任何一个关键字出现且只出现在一个结点中;
3. 搜索有可能在非叶子结点结束;
4. 其搜索性能等价于在关键字全集内做一次二分查找;
5. 自动层次控制;
由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:


其中,M为设定的非叶子结点最多子树个数,N为关键字总数;
所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;
由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;

B+

B+树是B-树的变体,也是一种多路搜索树:
1. 其定义基本与B-树同,除了:
2. 非叶子结点的子树指针与关键字个数相同;
3. 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
5. 为所有叶子结点增加一个链指针;
6. 所有关键字都在叶子结点出现;
如(M=3):


B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;
B+的特性:
1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
2. 不可能在非叶子结点命中;
3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
4. 更适合文件索引系统;

B*

B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针:

B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);
B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;
所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

小结

B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点;
B-树:多路搜索树,每个结点存储M/2M个关键字,非叶子结点存储指向关键字范围的子结点;
所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;
B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;
B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3

详解 B-Tree 与B+Tree

 1、什么是B-TreeB-tree又叫平衡多路查找树。

一棵m阶的B-tree (m叉树)的特性如下:

    1) 树中每个结点至多有m个孩子;

    2) 除根结点和叶子结点外,其它每个结点至少有[m / 2]向上取整个孩子;

    3) 若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);

    4) 所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点,实际上这些结点不存在,指向这些结点的指针都为null);

    5) 每个非终端结点中包含有n个关键字信息: (n,P0,K1,P1,K2,P2,……,Kn,Pn)。其中:a)   Ki (i=1…n)为关键字,且关键字按顺序排序K(i-1)< Ki。         b)   Pi为指向子树根的接点,且指针P(i-1)指向子树中所有结点的关键字均小于Ki,但都大于K(i-1)。         c)   关键字的个数n必须满足: [m / 2]-1 <= n <= m-1。    

备注:在此处[ ]中的运算表示向上取整下面是B-Tree的结构示例图:  

2.jpg

一个为m阶的B-Tree,设其索引N个key,则其树高h的上限为logm((N+1)/2),检索一个key,其查找节点个数的渐进复杂度为O(logmN)。从这点可以看出,B-Tree是一个非常有效率的索引数据结构。 
 

2、什么是B+Tree  
B+tree:是B-tree的变形树。

一棵m阶的B+tree和m阶的B-tree的差异在于:

    1.有n棵子树的结点中含有n个关键字; (B-tree是n棵子树有n-1个关键字)

    2.所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。 (B-tree的叶子节点并没有包括全部需要查找的信息)

    3.所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (B-tree的非终节点也包含需要查找的有效信息) 
B+树的结构示例图如下:

3.jpg

3、B+Tree与B-Tree 的区别
 1)B-树的关键字和记录是放在一起的,叶子节点可以看作外部节点,不包含任何信息;B+树的非叶子节点中只有关键字和指向下一个节点的索引,记录只放在叶子节点中。  

    2)在B-树中,越靠近根节点的记录查找时间越快,只要找到关键字即可确定记录的存在;而B+树中每个记录的查找时间基本是一样的,都需要从根节点走到叶子节点,而且在叶子节点中还要再比较关键字。从这个角度看B-树的性能好像要比B+树好,而在实际应用中却是B+树的性能要好些。因为B+树的非叶子节点不存放实际的数据,这样每个节点可容纳的元素个数比B-树多,树高比B-树小,这样带来的好处是减少磁盘访问次数。尽管B+树找到一个记录所需的比较次数要比B-树多,但是一次磁盘访问的时间相当于成百上千次内存比较的时间,因此实际中B+树的性能可能还会好些,而且B+树的叶子节点使用指针连接在一起,方便顺序遍历(例如查看一个目录下的所有文件,一个表中的所有记录等),这也是很多数据库和文件系统使用B+树的缘故。

 

思考:为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引? 

1) B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。 

2) B+树的查询效率更加稳定 
  由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。