数据库中INFORMATION_SCHEMA的说明及使用

第一个查询看看库里有多少个表,表名等

select * from INFORMATION_SCHEMA.TABLES

information_schema这张数据表保存了MySQL服务器所有数据库的信息。如数据库名,数据库的表,表栏的数据类型与访问权限等。再简单点,这台MySQL服务器上,到底有哪些数据库、各个数据库有哪些表,每张表的字段类型是什么,各个数据库要什么权限才能访问,等等信息都保存在information_schema表里面。

Mysql的INFORMATION_SCHEMA数据库包含了一些表和视图,提供了访问数据库元数据的方式。

元数据是关于数据的数据,如数据库名或表名,列的数据类型,或访问权限等。有些时候用于表述该信息的其他术语包括“数据词典”和“系统目录”。

 

下面对一些重要的数据字典表做一些说明:

SCHEMATA表:提供了关于数据库的信息。

TABLES表:给出了关于数据库中的表的信息。

COLUMNS表:给出了表中的列信息。

STATISTICS表:给出了关于表索引的信息。

USER_PRIVILEGES表:给出了关于全程权限的信息。该信息源自mysql.user授权表。

SCHEMA_PRIVILEGES表:给出了关于方案(数据库)权限的信息。该信息来自mysql.db授权表。

TABLE_PRIVILEGES表:给出了关于表权限的信息。该信息源自mysql.tables_priv授权表。

COLUMN_PRIVILEGES表:给出了关于列权限的信息。该信息源自mysql.columns_priv授权表。

CHARACTER_SETS表:提供了关于可用字符集的信息。

COLLATIONS表:提供了关于各字符集的对照信息。

COLLATION_CHARACTER_SET_APPLICABILITY表:指明了可用于校对的字符集。

TABLE_CONSTRAINTS表:描述了存在约束的表。

KEY_COLUMN_USAGE表:描述了具有约束的键列。

ROUTINES表:提供了关于存储子程序(存储程序和函数)的信息。此时,ROUTINES表不包含自定义函数(UDF)。

VIEWS表:给出了关于数据库中的视图的信息。

TRIGGERS表:提供了关于触发程序的信息。

由浅入深理解索引的实现

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

MySQL ACID及四种隔离级别的解释

以下内容出自《高性能MySQL》第三版,了解事务的ACID及四种隔离级有助于我们更好的理解事务运作。

下面举一个银行应用是解释事务必要性的一个经典例子。假如一个银行的数据库有两张表:支票表(checking)和储蓄表(savings)。现在要从用户Jane的支票账户转移200美元到她的储蓄账户,那么至少需要三个步骤:

1、检查支票账户的余额高于或者等于200美元。

2、从支票账户余额中减去200美元。

3、在储蓄帐户余额中增加200美元。

上述三个步骤的操作必须打包在一个事务中,任何一个步骤失败,则必须回滚所有的步骤。

 

可以用START TRANSACTION语句开始一个事务,然后要么使用COMMIT提交将修改的数据持久保存,要么使用ROLLBACK撤销所有的修改。事务SQL的样本如下:

1. start transaction;

2. select balance from checking where customer_id = 10233276;

3. update checking set balance = balance – 200.00 where customer_id = 10233276;

4. update savings set balance = balance + 200.00 where customer_id = 10233276;

5. commit;

 

ACID表示原子性(atomicity)、一致性(consistency)、隔离性(isolation)和持久性(durability)。一个很好的事务处理系统,必须具备这些标准特性:

 

原子性(atomicity)

  一个事务必须被视为一个不可分割的最小工作单元,整个事务中的所有操作要么全部提交成功,要么全部失败回滚,对于一个事务来说,不可能只执行其中的一部分操作,这就是事务的原子性

一致性(consistency)

     数据库总是从一个一致性的状态转换到另一个一致性的状态。(在前面的例子中,一致性确保了,即使在执行第三、四条语句之间时系统崩溃,支票账户中也不会损失200美元,因为事务最终没有提交,所以事务中所做的修改也不会保存到数据库中。)

隔离性(isolation)

     通常来说,一个事务所做的修改在最终提交以前,对其他事务是不可见的。(在前面的例子中,当执行完第三条语句、第四条语句还未开始时,此时有另外的一个账户汇总程序开始运行,则其看到支票帐户的余额并没有被减去200美元。)

持久性(durability)

  一旦事务提交,则其所做的修改不会永久保存到数据库。(此时即使系统崩溃,修改的数据也不会丢失。持久性是个有占模糊的概念,因为实际上持久性也分很多不同的级别。有些持久性策略能够提供非常强的安全保障,而有些则未必,而且不可能有能做到100%的持久性保证的策略。)

 

隔离级别:

READ UNCOMMITTED(未提交读)

  在READ UNCOMMITTED级别,事务中的修改,即使没有提交,对其他事务也都是可见的。事务可以读取未提交的数据,这也被称为脏读(Dirty Read)。这个级别会导致很多问题,从性能上来说,READ UNCOMMITTED不会比其他的级别好太多,但却缺乏其他级别的很多好处,除非真的有非常必要的理由,在实际应用中一般很少使用。

READ COMMITTED(提交读)

  大多数数据库系统的默认隔离级别都是READ COMMTTED(但MySQL不是)。READ COMMITTED满足前面提到的隔离性的简单定义:一个事务开始时,只能"看见"已经提交的事务所做的修改。换句话说,一个事务从开始直到提交之前,所做的任何修改对其他事务都是不可见的。这个级别有时候叫做不可重复读(nonrepeatble read),因为两次执行同样的查询,可能会得到不一样的结果

REPEATABLE READ(可重复读)

  REPEATABLE READ解决了脏读的问题。该隔离级别保证了在同一个事务中多次读取同样记录结果是一致的。但是理论上,可重复读隔离级别还是无法解决另外一个幻读(Phantom Read)的问题。所谓幻读,指的是当某个事务在读取某个范围内的记录时,另一个事务又在该范围内插入了新的记录,当之前的事务再次读取该范围的记录时,会产生幻行(Phantom Row)。InnoDB和XtraDB存储引擎通过多版本并发控制(MVCC,Multiversion Concurrency Control)解决了幻读的问题。

SERIALIZABLE(可串行化)

  SERIALIZABLE是最高的隔离级别。它通过强制事务串行执行,避免了前面说的幻读的问题。简单来说,SERIALIZABLE会在读取每一行数据都加锁,所以可能导致大量的超时和锁争用问题。实际应用中也很少用到这个隔离级别,只有在非常需要确保数据的一致性而且可以接受没有并发的情况下,才考虑采用该级别。

打钩说明该隔离级别还存在这种情况,打X代表该隔离级别已经解决了这种情况:022015137336388.jpg

MyISAM引擎和InnoDB引擎的特点

随着MySQL的不断更新,由于各存储引擎功能特性差异较大,这篇文章主要是介绍如何来选择合适的存储引擎来应对不同的业务场景,朋友们可以根据业务需求,选择合适的存储引擎。^.^

MyISAM

特性

不支持事务:MyISAM存储引擎不支持事务,所以对事务有要求的业务场景不能使用

表级锁定:其锁定机制是表级索引,这虽然可以让锁定的实现成本很小但是也同时大大降低了其并发性能

读写互相阻塞:不仅会在写入的时候阻塞读取,MyISAM还会在读取的时候阻塞写入,但读本身并不会阻塞另外的读

只会缓存索引:MyISAM可以通过key_buffer缓存以大大提高访问性能减少磁盘IO,但是这个缓存区只会缓存索引,而不会缓存数据

适用场景

不需要事务支持(不支持)

并发相对较低(锁定机制问题)

数据修改相对较少(阻塞问题)

以读为主

数据一致性要求不是非常高

最佳实践

尽量索引(缓存机制)

调整读写优先级,根据实际需求确保重要操作更优先

启用延迟插入改善大批量写入性能

尽量顺序操作让insert数据都写入到尾部,减少阻塞

分解大的操作,降低单个操作的阻塞时间

降低并发数,某些高并发场景通过应用来进行排队机制

对于相对静态的数据,充分利用Query Cache可以极大的提高访问效率

MyISAM的Count只有在全表扫描的时候特别高效,带有其他条件的count都需要进行实际的数据访问

InnoDB

特性

具有较好的事务支持:支持4个事务隔离级别,支持多版本读

行级锁定:通过索引实现,全表扫描仍然会是表锁,注意间隙锁的影响

读写阻塞与事务隔离级别相关

具有非常高效的缓存特性:能缓存索引,也能缓存数据

整个表和主键以Cluster方式存储,组成一颗平衡树

所有Secondary Index都会保存主键信息

适用场景

需要事务支持(具有较好的事务特性)

行级锁定对高并发有很好的适应能力,但需要确保查询是通过索引完成

数据更新较为频繁的场景

数据一致性要求较高

硬件设备内存较大,可以利用InnoDB较好的缓存能力来提高内存利用率,尽可能减少磁盘 IO

最佳实践

主键尽可能小,避免给Secondary index带来过大的空间负担

避免全表扫描,因为会使用表锁

尽可能缓存所有的索引和数据,提高响应速度

在大批量小插入的时候,尽量自己控制事务而不要使用autocommit自动提交

合理设置innodb_flush_log_at_trx_commit参数值,不要过度追求安全性

避免主键更新,因为这会带来大量的数据移动

NDBCluster

特性

分布式:分布式存储引擎,可以由多个NDBCluster存储引擎组成集群分别存放整体数据的一部分

支持事务:和Innodb一样,支持事务

可与mysqld不在一台主机:可以和mysqld分开存在于独立的主机上,然后通过网络和mysqld通信交互

内存需求量巨大:新版本索引以及被索引的数据必须存放在内存中,老版本所有数据和索引必须存在与内存中

适用场景

具有非常高的并发需求

对单个请求的响应并不是非常的critical

查询简单,过滤条件较为固定,每次请求数据量较少,又不希望自己进行水平Sharding

最佳实践

尽可能让查询简单,避免数据的跨节点传输

尽可能满足SQL节点的计算性能,大一点的集群SQL节点会明显多余Data节点

在各节点之间尽可能使用万兆网络环境互联,以减少数据在网络层传输过程中的延时

想了解更多关于MyISAM和InnoDB的性能对比,可以参考Percona的这个

http://www.percona.com/blog/2007/01/08/innodb-vs-myisam-vs-falcon-benchmarks-part-1/

http://imysql.com/2014/11/01/mysql-faq-convert-myisam-to-innodb-tips.shtml

设计模式 – 观察者模式

 

观察者模式 Observer

  观察者模式定义了一种一对多的依赖关系,让多个观察者对象同时监听某一个主题对象。

  这个主题对象在状态上发生变化时,会通知所有观察者对象,让它们能够自动更新自己。

 

观察者模式的组成

  抽象主题角色:把所有对观察者对象的引用保存在一个集合中,每个抽象主题角色都可以有任意数量的观察者。抽象主题提供一个接口,可以增加和删除观察者角色。一般用一个抽象类和接口来实现。

  抽象观察者角色:为所有具体的观察者定义一个接口,在得到主题的通知时更新自己。

  具体主题角色:在具体主题内部状态改变时,给所有登记过的观察者发出通知。具体主题角色通常用一个子类实现。

  具体观察者角色:该角色实现抽象观察者角色所要求的更新接口,以便使本身的状态与主题的状态相协调。通常用一个子类实现。如果需要,具体观察者角色可以保存一个指向具体主题角色的引用。

 

程序实例

  通过程序实例来说明观察者模式:

  首先定义抽象的观察者:

//抽象观察者角色public interface Watcher
{    public void update(String str);

}

        然后定义抽象的主题角色,即抽象的被观察者,在其中声明方法(添加、移除观察者,通知观察者):

//抽象主题角色,watched:被观察
public interface Watched
{
    public void addWatcher(Watcher watcher);

    public void removeWatcher(Watcher watcher);

    public void notifyWatchers(String str);

}

        然后定义具体的观察者:

public class ConcreteWatcher implements Watcher
{

    @Override
    public void update(String str)
    {
        System.out.println(str);
    }

}

  之后是具体的主题角色: 

import java.util.ArrayList;
import java.util.List;

public class ConcreteWatched implements Watched
{
    // 存放观察者
    private List<Watcher> list = new ArrayList<Watcher>();

    @Override
    public void addWatcher(Watcher watcher)
    {
        list.add(watcher);
    }

    @Override
    public void removeWatcher(Watcher watcher)
    {
        list.remove(watcher);
    }

    @Override
    public void notifyWatchers(String str)
    {
        // 自动调用实际上是主题进行调用的
        for (Watcher watcher : list)
        {
            watcher.update(str);
        }
    }

}

  编写测试类:

public class Test
{
    public static void main(String[] args)
    {
        Watched girl = new ConcreteWatched();
        
        Watcher watcher1 = new ConcreteWatcher();
        Watcher watcher2 = new ConcreteWatcher();
        Watcher watcher3 = new ConcreteWatcher();
        
        girl.addWatcher(watcher1);
        girl.addWatcher(watcher2);
        girl.addWatcher(watcher3);
        
        girl.notifyWatchers("开心");
    }

}

设计模式 – 策略者模式

<?php

abstract class Expression{
    private static $keycount=0;
    private $key;
    abstract function interpret( InterpreterContext $context);

    public function getKey(){

        if(@!assert($this->key)){
            self::$keycount++;
            $this->key=self::$keycount;
        }

        return $this->key;
    }
}

class LiteralExpression extends Expression{
    private $value;
    function __construct($value){
        $this->value = $value;
    }

    function interpret(InterpreterContext $context){
        $context->replace($this, $this->value);

        echo $this->getKey().'<br>';
    }
}

class InterpreterContext{
    private $expressionstore = array();

    function replace(Expression $exp, $value){
        $this->expressionstore[$exp->getKey()] = $value;
    }

    function lookup(Expression $exp){
        return $this->expressionstore[$exp->getKey()];
    }
}

$context = new InterpreterContext();
$literal = new LiteralExpression('four');
$literal->interpret($context);


$literal2 = new LiteralExpression('xxxxx');
$literal2->interpret($context);

echo $context->lookup($literal).'<br />';
echo $context->lookup($literal2).'<br />';
echo $context->lookup($literal2).'<br />';
?>

1.概述

        在软件开发中也常常遇到类似的情况,实现某一个功能有多种算法或者策略,我们可以根据环境或者条件的不同选择不同的算法或者策略来完成该功能。如查找、排序等,一种常用的方法是硬编码(Hard Coding)在一个类中,如需要提供多种查找算法,可以将这些算法写到一个类中,在该类中提供多个方法,每一个方法对应一个具体的查找算法;当然也可以将这些查找算法封装在一个统一的方法中,通过if…else…或者case等条件判断语句来进行选择。这两种实现方法我们都可以称之为硬编码,如果需要增加一种新的查找算法,需要修改封装算法类的源代码;更换查找算法,也需要修改客户端调用代码。在这个算法类中封装了大量查找算法,该类代码将较复杂,维护较为困难。如果我们将这些策略包含在客户端,这种做法更不可取,将导致客户端程序庞大而且难以维护,如果存在大量可供选择的算法时问题将变得更加严重。

例子1:一个菜单功能能够根据用户的“皮肤”首选项来决定是否采用水平的还是垂直的排列形式。同事可以灵活增加菜单那的显示样式。

例子2:出行旅游:我们可以有几个策略可以考虑:可以骑自行车,汽车,做火车,飞机。每个策略都可以得到相同的结果,但是它们使用了不同的资源。选择策略的依据是费用,时间,使用工具还有每种方式的方便程度 。

1336731431_2462.png

2.问题

如何让算法和对象分开来,使得算法可以独立于使用它的客户而变化?

3.解决方案

策略模式:定义一系列的算法,把每一个算法封装起来, 并且使它们可相互替换。本模式使得算法可独立于使用它的客户而变化。也称为政策模式(Policy)。(Definea family of algorithms,encapsulate each one, andmake them interchangeable. Strategy lets the algorithmvary independently from clients that use it. )

策略模式把对象本身和运算规则区分开来,其功能非常强大,因为这个设计模式本身的核心思想就是面向对象编程的多形性的思想。

4.适用性

当存在以下情况时使用Strategy模式

1)• 许多相关的类仅仅是行为有异。 “策略”提供了一种用多个行为中的一个行为来配置一个类的方法。即一个系统需要动态地在几种算法中选择一种。

2)• 需要使用一个算法的不同变体。例如,你可能会定义一些反映不同的空间 /时间权衡的算法。当这些变体实现为一个算法的类层次时 ,可以使用策略模式。

3)• 算法使用客户不应该知道的数据。可使用策略模式以避免暴露复杂的、与算法相关的数据结构。

4)• 一个类定义了多种行为 , 并且这些行为在这个类的操作中以多个条件语句的形式出现。将相关的条件分支移入它们各自的Strategy类中以代替这些条件语句。

5.结构

1336732187_4598.jpg

6.模式的组成

环境类(Context):用一个ConcreteStrategy对象来配置。维护一个对Strategy对象的引用。可定义一个接口来让Strategy访问它的数据。

抽象策略类(Strategy):定义所有支持的算法的公共接口。 Context使用这个接口来调用某ConcreteStrategy定义的算法。

具体策略类(ConcreteStrategy):以Strategy接口实现某具体算法。

7.效果

Strategy模式有下面的一些优点:

1) 相关算法系列 Strategy类层次为Context定义了一系列的可供重用的算法或行为。 继承有助于析取出这些算法中的公共功能。

2) 提供了可以替换继承关系的办法: 继承提供了另一种支持多种算法或行为的方法。你可以直接生成一个Context类的子类,从而给它以不同的行为。但这会将行为硬行编制到 Context中,而将算法的实现与Context的实现混合起来,从而使Context难以理解、难以维护和难以扩展,而且还不能动态地改变算法。最后你得到一堆相关的类 , 它们之间的唯一差别是它们所使用的算法或行为。 将算法封装在独立的Strategy类中使得你可以独立于其Context改变它,使它易于切换、易于理解、易于扩展。

3) 消除了一些if else条件语句 :Strategy模式提供了用条件语句选择所需的行为以外的另一种选择。当不同的行为堆砌在一个类中时 ,很难避免使用条件语句来选择合适的行为。将行为封装在一个个独立的Strategy类中消除了这些条件语句。含有许多条件语句的代码通常意味着需要使用Strategy模式。

4) 实现的选择 Strategy模式可以提供相同行为的不同实现。客户可以根据不同时间 /空间权衡取舍要求从不同策略中进行选择。

Strategy模式缺点:

1)客户端必须知道所有的策略类,并自行决定使用哪一个策略类:  本模式有一个潜在的缺点,就是一个客户要选择一个合适的Strategy就必须知道这些Strategy到底有何不同。此时可能不得不向客户暴露具体的实现问题。因此仅当这些不同行为变体与客户相关的行为时 , 才需要使用Strategy模式。

2 ) Strategy和Context之间的通信开销 :无论各个ConcreteStrategy实现的算法是简单还是复杂, 它们都共享Strategy定义的接口。因此很可能某些 ConcreteStrategy不会都用到所有通过这个接口传递给它们的信息;简单的 ConcreteStrategy可能不使用其中的任何信息!这就意味着有时Context会创建和初始化一些永远不会用到的参数。如果存在这样问题 , 那么将需要在Strategy和Context之间更进行紧密的耦合。

3 )策略模式将造成产生很多策略类:可以通过使用享元模式在一定程度上减少对象的数量。 增加了对象的数目 Strategy增加了一个应用中的对象的数目。有时你可以将 Strategy实现为可供各Context共享的无状态的对象来减少这一开销。任何其余的状态都由 Context维护。Context在每一次对Strategy对象的请求中都将这个状态传递过去。共享的 Strategy不应在各次调用之间维护状态。

8.实现

<?php  
/** 
* 策略模式 
* 定义一系列的算法,把每一个算法封装起来, 并且使它们可相互替换。本模式使得算法可独立于使用它的客户而变化 
* 
*/   
  
  
/** 
* 出行旅游 
* 
*  
*/  
interface TravelStrategy{  
    public function travelAlgorithm();  
}   
  
  
/** 
 * 具体策略类(ConcreteStrategy)1:乘坐飞机 
 */  
class AirPlanelStrategy implements TravelStrategy {  
    public function travelAlgorithm(){  
        echo "travel by AirPlain", "<BR>\r\n";   
    }  
}   
  
  
/** 
 * 具体策略类(ConcreteStrategy)2:乘坐火车 
 */  
class TrainStrategy implements TravelStrategy {  
    public function travelAlgorithm(){  
        echo "travel by Train", "<BR>\r\n";   
    }  
}   
  
/** 
 * 具体策略类(ConcreteStrategy)3:骑自行车 
 */  
class BicycleStrategy implements TravelStrategy {  
    public function travelAlgorithm(){  
        echo "travel by Bicycle", "<BR>\r\n";   
    }  
}   
  
  
  
/** 
 *  
 * 环境类(Context):用一个ConcreteStrategy对象来配置。维护一个对Strategy对象的引用。可定义一个接口来让Strategy访问它的数据。 
 * 算法解决类,以提供客户选择使用何种解决方案: 
 */  
class PersonContext{  
    private $_strategy = null;  
  
    public function __construct(TravelStrategy $travel){  
        $this->_strategy = $travel;  
    }  
    /** 
    * 旅行 
    */  
    public function setTravelStrategy(TravelStrategy $travel){  
        $this->_strategy = $travel;  
    }  
    /** 
    * 旅行 
    */  
    public function travel(){  
        return $this->_strategy ->travelAlgorithm();  
    }  
}   
  
// 乘坐火车旅行  
$person = new PersonContext(new TrainStrategy());  
$person->travel();  
  
// 改骑自行车  
$person->setTravelStrategy(new BicycleStrategy());  
$person->travel();  
  
?>

2)排序策略:某系统提供了一个用于对数组数据进行操作的类,该类封装了对数组的常见操作,

如查找数组元素、对数组元素进行排序等。现以排序操作为例,使用策略模式设计该数组操作类,

使得客户端可以动态地更换排序算法,可以根据需要选择冒泡排序或选择排序或插入排序,

也能够灵活地增加新的排序算法。