转:leveldb 的实现

作者:Jeff Dean, Sanjay Ghemawat

原文:http://leveldb.googlecode.com/svn/trunk/doc/impl.html

译者:phylips@bmy 2011-8-17

出处:http://duanple.blog.163.com/blog/static/7097176720112643946178/

Files

LevelDB的实现本质上类似于Bigtable中的tablet(参见Bigtable论文5.3节)。但是,与论文中的具体的文件组织方式稍有不同,解释如下:

每个数据库由一组存储在指定目录下的一个文件集合组成。有如下几种文件类型:

Log files

日志文件(*.log)存储了最近的一系列更新。每个更新操作会被追加到当前的日志文件中。当日志文件达到预定义的大小后,会被转化为一个sorted table,同时一个新的日志文件会被创建出来以接受未来的更新。

同时会在一个内存结构(memtable)中保存一份当前的日志文件的一个copy。该copy会参与到每次读操作中,这样最新的已日志化的更新就能够反映到读操作中。

Sorted tables

sorted table (*.sst) 存储了一系列根据key值排好序的记录。每条记录要么是某key值对应的value,要么是一个针对该key值的删除标记。(删除标记会被用来去掉那些老的sorted tables中已过时的value值)。

sorted tables集合是通过一系列的level来进行组织的。从日志文件生成的sorted table会被放置在一个特殊的young level(也称作level 0)内。当该level下的文件数超过一定阈值(当前是4)时,该level下的所有文件会与level 1下与之有重叠的那些文件merge到一块,从而产生一系列新的level 1下的文件(我们会为每2MB的数据创建一个level 1文件)。

在level 0下的不同文件可能包含重叠的key值。但是其他level下的文件,它们的key range都是不重叠的(是指同一个level内部的文件不会重叠,不同的level之间会存在重叠)。设现有level L(L>=1),当level L下的文件总大小超过(10^L)MB时(比如,对应level 1就是10MB,level 2就是100MB,…),level L下的一个文件就会与level L+1下的所有与它有重叠的key的文件merge成一系列level L+1下的新文件。为最小化昂贵的seek开销,这些merge操作通过批量的读写操作,逐步的将新的更新从young level迁移到最大的level下。

Manifest

MANIFEST文件列出了组成每个level的sorted tables集合,对应的key range,以及其他一些重要的元数据。只要数据库被重新打开,就会产生一个新的MANIFEST文件(文件名会嵌入一个新的数字)。MANIFEST文件会被格式化为一个log,所有导致状态改变(文件增加或删除)的变更都会追加到该log里。

Current

CURRENT 是一个包含了最新的MANIFEST文件名称的文本文件。

Info logs

一些信息会被输出到名为LOG及LOG.old的文件中。
Others

其他用于各种目的的可能会产生的文件 (LOCK, *.dbtmp).

Level 0

当日志文件超过一定大小(默认1MB)时,会进行如下操作:

l  创建一个全新的memtable结构和log文件,同时将未来的更新指向它们

l  同时在后台进行如下操作:

?  将之前的memtable的内容写入到sstable里

?  丢弃该memtable

?  删除老的log文件及memtable

?  将新的sstable添加到level 0下

Compactions

当level L的大小超过自身的限制时,我们会在一个后台线程中进行compact操作。该操作会选择来自level L的一个文件,以及那些level L+1中所有与该文件重叠的文件。需要注意的是,即使level L下的这个文件只与level L+1下的某文件的一部分有重叠,也需要读取整个level L+1下的那个文件进行compaction,之后这个旧的level L+1下的文件就会被丢弃。另外:因为level 0很特殊(文件相互之间可能是有重叠的),因此对于从level 0到level 1的compaction需要特殊对待:当level 0的某些文件相互重叠时,它的compaction就需要选择不止一个level 0的下的文件。Compaction会merge它选定的那些文件产生一系列新的level L+1下的文件。当当前输出文件大小达到目标大小(2MB)时,我们就会产生出一个新的level L+1下的文件。另外当当前输出文件的key range已经大的与10个以上的level L+2下的文件有重叠时,我们也会立即产生出一个新文件,而不一定非要等到它达到2MB,这是为了保证后面针对level L+1的Compaction不会从level L+2下获取过多数据。

老的文件会被丢弃,新的文件会被添加到服务状态。针对特定level下的Compaction是在整个key值空间内螺旋式地进行的。详细来说,比如对于Level L,我们会记住它上次compaction的那个最后的key值,在对于Level L的下次compaction时,我们会选择排在该key之后的第一个文件开始(如果没有这样的文件,那我们就再从头开始)。

Compaction会丢弃掉被覆盖的那些value值。同时如果更高level下的文件的key range不包含当前key时,针对它的删除标记也可以被丢弃掉{!更高level下的文件实际上是一些更老的值,如果它们包含该key,那么如果我们丢弃该低level下的删除标记,会导致该删除操作的丢失}

Timing

Level 0的compaction可能会从level 0下读取最多4个1MB文件,以及最坏情况下会读取所有的level 1下的文件(10MB),这意味着,我们可能需要读14MB,写14MB。

除了比较特殊的Level 0的compaction,其他情况下我们会选取level L下的一个2MB的文件。最坏情况下,level L+1下可能有12个文件与它重叠(10是因为level L+1比level L大10倍,另外的2是因为在level L下的文件边界通常与level L+1下的边界并不是对其的)。因此compaction会读26MB,写26MB。假设磁盘IO带宽是100MB/s,最坏情况下的compaction可能需要大概0.5秒。

如果我们对后台操作进行一些限制,比如限制在全部IO带宽的10%,那么compaction时间可能会达到5秒。如果用户在用户以10MB/s的速度写入,我们就可能会创建出大量的level 0下的文件(可能会达到50,因为compaction需要5秒,而5秒内客户端已经又写入了50MB,而每个1MB,因此是50个)。这可能会显著增加读操作的开销,因为每次读操作都需要merge更多的文件。

解决方案 1:为了减少这种问题,我们可以在level-0下的文件数很大的时候,增加log切换的阈值。缺点是,阈值越大,相对应的memtable用掉的内存也就会越多。

解决方案2: 当level 0下的文件数上升很快时,我们可以人为地降低写操作速率。

解决方案3: 尽量降低merge的开销。由于大多数的level 0下的文件的block都已经缓存在cache里了,因此我们只需要关注merge迭代过程中的O(N)的复杂度。

Number of files

为降低文件数,我们可以为更高level下的文件使用更大的文件大小,取代固定的2MB文件。当然这可能导致更多的compactions过程中的波动。另外我们也可以将文件集合划分到多个目录下。

2011-02-04,我们在ext3文件系统下做了一个关于目录下的文件数与文件打开时间的关系的实验:

Files in directory   Microseconds to open a file

1000   9

10000  10

100000 16

看起来在现代文件系统中,没有必要进行目录切分。

Recovery

读取CURRENT文件找到最新提交的MANIFEST文件名
读取该 MANIFEST文件
清空垃圾文件
我们可以打开所有的sstable,但是使用惰性加载的方式会更好些…
将日志转化为一个新的level 0下的sstable
Start directing new writes to a new log file with recovered sequence#
Garbage collection of files

DeleteObsoleteFiles()会在每次compaction结束及recovery结束后调用。它会找到数据库中所有文件的名称。删掉除当前日志文件的所有日志文件。删掉那些不属于任何level及任何活动的compaction输出的table文件。

Immutable table文件格式

文件格式如下:

===========

<beginning_of_file>

[data block 1]

[data block 2]

[data block N]

[meta block 1]

[meta block K]

[metaindex block]

[index block]

[Footer]        (fixed size; starts at file_size – sizeof(Footer))

<end_of_file>

文件包含一些内部指针。每个这样的指针被称为一个BlockHandle,包含如下信息:

offset:          varint64

size:            varint64

(1)文件内的key/value对序列有序排列,然后划分到一系列的data blocks里。这些blocks一个接一个的分布在文件的开头。每个data block会根据block_builder.cc里的代码进行格式化,然后进行可选地压缩。

(2)在数据blocks之后存储的一些meta blocks,目前支持的meta block类型会在下面进行描述。未来也可能添加更多的meta block类型。每个meta block也会根据block_builder.cc里的代码进行格式化,然后进行可选地压缩。

(3) A “metaindex” block.会为每个meta block保存一条记录,记录的key值就是meta block的名称,value值就是指向该meta block的一个BlockHandle。

(4) An “index” block.  会为每个data block保存一条记录,key值是>=对应的data block里最后那个key值,同时在后面的那个data block第一个key值之前的那个key值,value值就是指向该meta block的一个BlockHandle。

(5) 文件的最后是一个定长的footer,包含了metaindex和index这两个blocks的BlockHandle,以及一个magic number。

metaindex_handle:    char[p];    // Block handle for metaindex

index_handle:        char[q];    // Block handle for index

padding:             char[40-p-q]; // 0 bytes to make fixed length

// (40==2*BlockHandle::kMaxEncodedLength)

magic:                 fixed64;    // == 0xdb4775248b80fb57

 

“stats” Meta Block

——————

该meta block包含一系列统计信息。Key就是该统计单元的名称,value包含一系列统计信息如下:

data size

index size

key size (uncompressed)

value size (uncompressed)

number of entries

number of data blocks

日志文件格式

日志文件内容由一系列的32KB blocks组成。唯一的异常是文件的末尾可能只包含一个部分块。每个block由一系列记录组成:
   block := record* trailer?
{!‘*’可以看做是正则表达式里的*,代表0个或n个record。‘?’也是,代表0个或者1个trailer }
   record :=
        checksum: uint32       // crc32c of type and data[]
        length: uint16
        type: uint8            // One of FULL, FIRST, MIDDLE, LAST
        data: uint8[length]
一条记录永远都不会从block的最后6个字节开始(因为它肯定放不下,看上面的记录checksum+length+type就占了7个字节了)。在这里组成trailer的最左处那些字节,要么完全是由0字节组成要么必须被读取者跳过。
此外: 如果当前block目前只剩下7个字节,然后现在需要添加一个非0长度的记录,那么写入者需要输出一个FIRST记录(不包含任何的用户数据)来填充该block剩余的7字节的空,然后将用户数据存放到下一个block里。
未来可以添加更多的类型。某些读取者可能会直接skip掉那些它不理解的记录,其他的一些可能会报告某些数据被skip掉了。
FULL == 1
FIRST == 2
MIDDLE == 3
LAST == 4
FULL 类型的记录包含了完整的用户记录.
FIRST, MIDDLE, LAST 用于那些被分成多个片段(通常是因为block的边界导致的)的用户记录的。FIRST表明是用户记录的第一个片段,FIRST表明是用户记录的最后一个片段,MID表明用户记录的中间片段类型。
Example: consider a sequence of user records:
   A: length 1000
   B: length 97270
   C: length 8000
A会作为一个FULL类型的记录存放在第一个block里。B 会被划分成三个片段:第一个片段会填充第一个block的剩余部分, 第二个片段会填充整个的第二个block, 第二个片段会填充第三个block的前面一部分. 最后,第三个block就只剩下6个字节,会作为trailer而留空。C将会作为一个FULL类型的记录存放在第四个block里。
===================
Some benefits over the recordio format:
(1) We do not need any heuristics for resyncing - just go to next block boundary and scan.  If there is a corruption, skip to the next block.  As a side-benefit, we do not get confused when part of the contents of one log file are embedded as a record inside another log file.
(2) Splitting at approximate boundaries (e.g., for mapreduce) is simple: find the next block boundary and skip records until we hit a FULL or FIRST record.
(3) We do not need extra buffering for large records.
Some downsides compared to recordio format:
(1) No packing of tiny records.  This could be fixed by adding a new record type, so it is a shortcoming of the current implementation,not necessarily the format.
(2) No compression.  Again, this could be fixed by adding new record types.

 

转:MySQL索引背后的数据结构及算法原理

写在前面的话

在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是不太赞同这句话(因为我觉得程序不仅仅是数据结构加算法),但是在日常的学习和工作中我确认深深感受到数据结构和算法的重要性,很多东西,如果你愿意稍稍往深处挖一点,那么扑面而来的一定是各种数据结构和算法知识。例如几乎每个程序员都要打交道的数据库,如果仅仅是用来存个数据、建建表、建建索引、做做增删改查,那么也许觉得数据结构和这东西没什么关系。不过要是哪天心血来潮,想知道的多一点,想研究一下如何优化数据库,那么一定避免不了研究索引的原理,如果想要真正明白索引是怎么工作的,如何合理的使用索引以优化数据库,那么就免不了纠结于一堆数据结构与算法之间了。所以,如果说“程序的核心基础 = 数据结构 + 算法”我是十分赞同的,而一个想成为高手的程序员,一定会去学习程序的核心基础。

好吧,说了这么多,其实我的意思是如果想把数据库索引学个明明白白,就必须将数据结构和算法作为切入点去学习,遗憾的是我目前还没有在网上找到从原理层面去介绍数据库索引的资料(这里仅指在通俗资料领域没找到,不包括学术论文),倒不是说没有高水平的程序员,就只在我们公司范围内能把这一点讲透彻讲明白的数据库大牛也海了去了,只是由于工作的忙碌和个人兴趣原因,这些大牛们没有时间或没有兴趣去写这方面的文章。由于工作的需要,我这个半桶水的程序员这段时间也草草研究一些关于MySQL数据库索引的东西,虽然对这方面的理解相比那些大牛差的太远了,不过这里我还是将这些浅薄的知识总结成文吧。

摘要

数据结构及算法基础

索引的本质

B-Tree和B+Tree

为什么实用B-Tree(B+Tree)

MySQL索引实现

MyISAM索引实现

InnoDB索引实现

索引使用策略及优化

示例数据库

最左前缀原理与相关优化

索引选择性与前缀索引

InnoDB的主键选择与插入优化

后记

参考文献

摘要

本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论。

文章主要内容分为四个部分。

第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。

第二部分结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。

第三部分根据上面的理论基础,讨论MySQL中高性能使用索引的策略。

数据结构及算法基础

索引的本质

MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。

我们知道,数据库查询是数据库的最主要功能之一,例如下面的SQL语句:

SELECT * FROM my_table WHERE col2 = '77'

可以从表“my_table”中获得“col2”为“77”的数据记录。

我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),遍历“my_table”然后逐行匹配“col2”的值是否是“77”,这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引

看一个例子:

image

图1

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

虽然这是一个货真价实的索引,但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black tree)实现的,原因会在下文介绍。

B-Tree和B+Tree

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构,在本文的下一节会结合存储器原理及计算机存取原理讨论为什么B-Tree和B+Tree在被如此广泛用于索引,这一节先单纯从数据结构角度描述它们。

B-Tree

为了描述B-Tree,首先定义一条数据记录为一个二元组[key, data],key为记录的键值,对于不同数据记录,key是互不相同的;data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构:

  1. d为大于1的一个正整数,称为B-Tree的度。
  2. h为一个正整数,称为B-Tree的高度。
  3. 每个非叶子节点由n-1个key和n个指针组成,其中d<=n<=2d。
  4. 每个叶子节点最少包含一个key和两个指针,最多包含2d-1个key和2d个指针,叶节点的指针均为null 。
  5. 所有叶节点具有相同的深度,等于树高h。
  6. key和指针互相间隔,节点两端是指针。
  7. 一个节点中的key从左到右非递减排列。
  8. 所有节点组成树结构。
  9. 每个指针要么为null,要么指向另外一个节点。
  10. 如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于v(key1),其中v(key1)为node的第一个key的值。
  11. 如果某个指针在节点node最右边且不为null,则其指向节点的所有key大于v(keym),其中v(keym)为node的最后一个key的值。
  12. 如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null,则其指向节点的所有key小于v(keyi+1)且大于v(keyi)。

图2是一个d=2的B-Tree示意图。

image

图2

由于B-Tree的特性,在B-Tree中按key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。B-Tree上查找算法的伪代码如下:

BTree_Search(node, key)
{
if(node == null) return null;
foreach(node.key)
{
if(node.key[i] == key) return node.data[i];
if(node.key[i] > key) return BTree_Search(point[i]->node);
}
return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);

关于B-Tree有一系列有趣的性质,例如一个度为d的B-Tree,设其索引N个key,则其树高h的上限为logd((N+1)/2),检索一个key,其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出,B-Tree是一个非常有效率的索引数据结构。

另外,由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质,本文不打算完整讨论B-Tree这些内容,因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法,有兴趣的朋友可以在本文末的参考文献一栏找到相应的资料进行阅读。

B+Tree

B-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比,B+Tree有以下不同点:

  1. 每个节点的指针上限为2d而不是2d+1。
  2. 内节点不存储data,只存储key;叶子节点不存储指针。

图3是一个简单的B+Tree示意。

image

图3

由于并不是所有节点都具有相同的域,因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同,虽然B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以在实现中B-Tree往往对每个节点申请同等大小的空间。

一般来说,B+Tree比B-Tree更适合实现外存储索引结构,具体原因与外存储器原理及计算机存取原理有关,将在下面讨论。

带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针。

image

图4

如图4所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能,例如图4中如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。

这一节对B-Tree和B+Tree进行了一个简单的介绍,下一节结合存储器存取原理介绍为什么目前B+Tree是数据库系统实现索引的首选数据结构。

为什么使用B-Tree(B+Tree)

上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。

image

图5

从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

主存的存取过程如下:

当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

磁盘存取原理

上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

图6是磁盘的整体结构示意图。

image

图6

一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

图7是磁盘结构的示意图。

image

图7

盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘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)。

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

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

上文还说过,B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小:

dmaxfloor(pagesize / (keysize + datasize + pointsize))   (pagesize – dmax >= pointsize)

dmaxfloor(pagesize / (keysize + datasize + pointsize)) – 1   (pagesize – dmax < pointsize)

floor表示向下取整。由于B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。

这一章从理论角度讨论了与索引相关的数据结构与算法问题,下一章将讨论B+Tree是如何具体实现为MySQL中索引,同时将结合MyISAM和InnDB存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。

MySQL索引实现

在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

image

图8

这里设表一共有三列,假设我们以Col1为主键,则图8是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:

image

图9

同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

image

图10

图10是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,图11为定义在Col3上的一个辅助索引:

image

图11

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

下一章将具体讨论这些与索引有关的优化策略。

索引使用策略及优化

MySQL的优化主要分为结构优化(Scheme optimization)和查询优化(Query optimization)。本章讨论的高性能索引策略主要属于结构优化范畴。本章的内容完全基于上文的理论基础,实际上一旦理解了索引背后的机制,那么选择高性能的策略就变成了纯粹的推理,并且可以理解这些策略背后的逻辑。

示例数据库

为了讨论索引策略,需要一个数据量不算小的数据库作为示例。本文选用MySQL官方文档中提供的示例数据库之一:employees。这个数据库关系复杂度适中,且数据量较大。下图是这个数据库的E-R关系图(引用自MySQL官方手册):

image

图12

MySQL官方文档中关于此数据库的页面为http://dev.mysql.com/doc/employee/en/employee.html。里面详细介绍了此数据库,并提供了下载地址和导入方法,如果有兴趣导入此数据库到自己的MySQL可以参考文中内容。

最左前缀原理与相关优化

高效使用索引的首要条件是知道什么样的查询会使用到索引,这个问题和B+Tree中的“最左前缀原理”有关,下面通过例子说明最左前缀原理。

这里先说一下联合索引的概念。在上文中,我们都是假设索引只引用了单个的列,实际上,MySQL中的索引可以以一定顺序引用多个列,这种索引叫做联合索引,一般的,一个联合索引是一个有序元组<a1, a2, …, an>,其中各个元素均为数据表的一列,实际上要严格定义索引需要用到关系代数,但是这里我不想讨论太多关系代数的话题,因为那样会显得很枯燥,所以这里就不再做严格定义。另外,单列索引可以看成联合索引元素数为1的特例。

以employees.titles表为例,下面先查看其上都有哪些索引:

SHOW INDEX FROM employees.titles;
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Null | Index_type |
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+
| titles |          0 | PRIMARY |            1 | emp_no      | A         | NULL |      | BTREE      |
| titles |          0 | PRIMARY |            2 | title       | A         | NULL |      | BTREE      |
| titles |          0 | PRIMARY |            3 | from_date   | A         |      443308 |      | BTREE      |
| titles |          1 | emp_no   |            1 | emp_no      | A         |      443308 |      | BTREE      |
+--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+

从结果中可以到titles表的主索引为<emp_no, title, from_date>,还有一个辅助索引<emp_no>。为了避免多个索引使事情变复杂(MySQL的SQL优化器在多索引时行为比较复杂),这里我们将辅助索引drop掉:

ALTER TABLE employees.titles DROP INDEX emp_no;

这样就可以专心分析索引PRIMARY的行为了。

情况一:全列匹配。

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title='Senior Engineer' AND from_date='1986-06-26';
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
| id | select_type | table | type  | possible_keys | key | key_len | ref               | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
|  1 | SIMPLE      | titles | const | PRIMARY | PRIMARY | 59      | const,const,const |    1 |       |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+

很明显,当按照索引中所有列进行精确匹配(这里精确匹配指“=”或“IN”匹配)时,索引可以被用到。这里有一点需要注意,理论上索引对顺序是敏感的,但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引,例如我们将where中的条件顺序颠倒:

EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26' AND emp_no='10001' AND title='Senior Engineer';
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
| id | select_type | table | type  | possible_keys | key | key_len | ref               | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
|  1 | SIMPLE      | titles | const | PRIMARY | PRIMARY | 59      | const,const,const |    1 |       |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+

效果是一样的。

情况二:最左前缀匹配。

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001';
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
| id | select_type | table | type | possible_keys | key | key_len | ref   | rows | Extra |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
|  1 | SIMPLE      | titles | ref  | PRIMARY | PRIMARY | 4       | const |    1 |       |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+

当查询条件精确匹配索引的左边连续一个或几个列时,如<emp_no>或<emp_no, title>,所以可以被用到,但是只能用到一部分,即条件所组成的最左前缀。上面的查询从分析结果看用到了PRIMARY索引,但是key_len为4,说明只用到了索引的第一列前缀。

情况三:查询条件用到了索引中列的精确匹配,但是中间某个条件未提供。

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26';
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref   | rows | Extra       |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | titles | ref  | PRIMARY | PRIMARY | 4       | const |    1 | Using where |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+

此时索引使用情况和情况二相同,因为title未提供,所以查询只用到了索引的第一列,而后面的from_date虽然也在索引中,但是由于title不存在而无法和左前缀连接,因此需要对结果进行扫描过滤from_date(这里由于emp_no唯一,所以不存在扫描)。如果想让from_date也使用索引而不是where过滤,可以增加一个辅助索引<emp_no, from_date>,此时上面的查询会使用这个索引。除此之外,还可以使用一种称之为“隔离列”的优化方法,将emp_no与from_date之间的“坑”填上。

首先我们看下title一共有几种不同的值:

SELECT DISTINCT(title) FROM employees.titles;
+--------------------+
| title              |
+--------------------+
| Senior Engineer    |
| Staff              |
| Engineer           |
| Senior Staff       |
| Assistant Engineer |
| Technique Leader   |
| Manager            |
+--------------------+

只有7种。在这种成为“坑”的列值比较少的情况下,可以考虑用“IN”来填补这个“坑”从而形成最左前缀:

EXPLAIN SELECT * FROM employees.titles
WHERE emp_no='10001'
AND title IN ('Senior Engineer', 'Staff', 'Engineer', 'Senior Staff', 'Assistant Engineer', 'Technique Leader', 'Manager')
AND from_date='1986-06-26';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY | PRIMARY | 59      | NULL |    7 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

这次key_len为59,说明索引被用全了,但是从type和rows看出IN实际上执行了一个range查询,这里检查了7个key。看下两种查询的性能比较:

SHOW PROFILES;
+----------+------------+-------------------------------------------------------------------------------+
| Query_ID | Duration   | Query                                                                         |
+----------+------------+-------------------------------------------------------------------------------+
|       10 | 0.00058000 | SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26'|
|       11 | 0.00052500 | SELECT * FROM employees.titles WHERE emp_no='10001' AND title IN ...          |
+----------+------------+-------------------------------------------------------------------------------+

“填坑”后性能提升了一点。如果经过emp_no筛选后余下很多数据,则后者性能优势会更加明显。当然,如果title的值很多,用填坑就不合适了,必须建立辅助索引。

情况四:查询条件没有指定索引第一列。

EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26';
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+

由于不是最左前缀,索引这样的查询显然用不到索引。

情况五:匹配某列的前缀字符串。

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title LIKE 'Senior%';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY | PRIMARY | 56      | NULL |    1 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

此时可以用到索引,但是如果通配符不是只出现在末尾,则无法使用索引。

情况六:范围查询。

EXPLAIN SELECT * FROM employees.titles WHERE emp_no<'10010' and title='Senior Engineer';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY | PRIMARY | 4       | NULL |   16 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

范围列可以用到索引(必须是最左前缀),但是范围列后面的列无法用到索引。同时,索引最多用于一个范围列,因此如果查询条件中有两个范围列则无法全用到索引。

EXPLAIN SELECT * FROM employees.titles
WHERE emp_no<'10010'
AND title='Senior Engineer'
AND from_date BETWEEN '1986-01-01' AND '1986-12-31';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY | PRIMARY | 4       | NULL |   16 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方,那就是仅用explain可能无法区分范围索引和多值匹配,因为在type中这两者都显示为range。同时,用了“between”并不意味着就是范围查询,例如下面的查询:

EXPLAIN SELECT * FROM employees.titles
WHERE emp_no BETWEEN '10001' AND '10010'
AND title='Senior Engineer'
AND from_date BETWEEN '1986-01-01' AND '1986-12-31';
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY | PRIMARY | 59      | NULL |   16 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

看起来是用了两个范围查询,但作用于emp_no上的“BETWEEN”实际上相当于“IN”,也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配,否则会对MySQL的行为产生困惑。

情况七:查询条件中含有函数或表达式。

很不幸,如果查询条件中含有函数或表达式,则MySQL不会为这列使用索引(虽然某些在数学意义上可以使用)。例如:

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND left(title, 6)='Senior';
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref   | rows | Extra       |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | titles | ref  | PRIMARY | PRIMARY | 4       | const |    1 | Using where |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+

虽然这个查询和情况五中功能相同,但是由于使用了函数left,则无法为title列应用索引,而情况五中用LIKE则可以。再如:

EXPLAIN SELECT * FROM employees.titles WHERE emp_no - 1='10000';
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+

显然这个查询等价于查询emp_no为10001的函数,但是由于查询条件是一个表达式,MySQL无法为其使用索引。看来MySQL还没有智能到自动优化常量表达式的程度,因此在写查询语句时尽量避免表达式出现在查询中,而是先手工私下代数运算,转换为无表达式的查询语句。

索引选择性与前缀索引

既然索引可以加快查询速度,那么是不是只要是查询语句需要,就建上索引?答案是否定的。因为索引虽然加快了查询速度,但索引也是有代价的:索引文件本身要消耗存储空间,同时索引会加重插入、删除和修改记录时的负担,另外,MySQL在运行时也要消耗资源维护索引,因此索引并不是越多越好。一般两种情况下不建议建索引。

第一种情况是表记录比较少,例如一两千条甚至只有几百条记录的表,没必要建索引,让查询做全表扫描就好了。至于多少条记录才算多,这个个人有个人的看法,我个人的经验是以2000作为分界线,记录数不超过 2000可以考虑不建索引,超过2000条可以酌情考虑索引。

另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性(Selectivity),是指不重复的索引值(也叫基数,Cardinality)与表记录数(#T)的比值:

Index Selectivity = Cardinality / #T

显然选择性的取值范围为(0, 1],选择性越高的索引价值越大,这是由B+Tree的性质决定的。例如,上文用到的employees.titles表,如果title字段经常被单独查询,是否需要建索引,我们看一下它的选择性:

SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;
+-------------+
| Selectivity |
+-------------+
|      0.0000 |
+-------------+

title的选择性不足0.0001(精确值为0.00001579),所以实在没有什么必要为其单独建索引。

有一种与索引选择性有关的索引优化策略叫做前缀索引,就是用列的前缀代替整个列作为索引key,当前缀长度合适时,可以做到既使得前缀索引的选择性接近全列索引,同时因为索引key变短而减少了索引文件的大小和维护开销。下面以employees.employees表为例介绍前缀索引的选择和使用。

从图12可以看到employees表只有一个索引<emp_no>,那么如果我们想按名字搜索一个人,就只能全表扫描了:

EXPLAIN SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido';
+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref  | rows | Extra       |
+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | employees | ALL | NULL | NULL | NULL | NULL | 300024 | Using where |
+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+

如果频繁按名字搜索员工,这样显然效率很低,因此我们可以考虑建索引。有两种选择,建<first_name>或<first_name, last_name>,看下两个索引的选择性:

SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
|      0.0042 |
+-------------+
SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
|      0.9313 |
+-------------+

<first_name>显然选择性太低,<first_name, last_name>选择性很好,但是first_name和last_name加起来长度为30,有没有兼顾长度和选择性的办法?可以考虑用first_name和last_name的前几个字符建立索引,例如<first_name, left(last_name, 3)>,看看其选择性:

SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
|      0.7879 |
+-------------+

选择性还不错,但离0.9313还是有点距离,那么把last_name前缀加到4:

SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
|      0.9007 |
+-------------+

这时选择性已经很理想了,而这个索引的长度只有18,比<first_name, last_name>短了接近一半,我们把这个前缀索引 建上:

ALTER TABLE employees.employees
ADD INDEX `first_name_last_name4` (first_name, last_name(4));

此时再执行一遍按名字查询,比较分析一下与建索引前的结果:

SHOW PROFILES;
+----------+------------+---------------------------------------------------------------------------------+
| Query_ID | Duration   | Query                                                                           |
+----------+------------+---------------------------------------------------------------------------------+
|       87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' |
|       90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' |
+----------+------------+---------------------------------------------------------------------------------+

性能的提升是显著的,查询速度提高了120多倍。

前缀索引兼顾索引大小和查询速度,但是其缺点是不能用于ORDER BY和GROUP BY操作,也不能用于Covering index(即当索引本身包含查询所需全部数据时,不再访问数据文件本身)。

InnoDB的主键选择与插入优化

在使用InnoDB存储引擎时,如果没有特别的需要,请永远使用一个与业务无关的自增字段作为主键。

经常看到有帖子或博客讨论主键选择问题,有人建议使用业务无关的自增主键,有人觉得没有必要,完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点,大多数论据都是业务层面的。如果从数据库索引优化角度看,使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。

上文讨论过InnoDB的索引实现,InnoDB使用聚集索引,数据记录本身被存于主索引(一颗B+Tree)的叶子节点上。这就要求同一个叶子节点内(大小为一个内存页或磁盘页)的各条数据记录按主键顺序存放,因此每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)。

如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:

image

图13

这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置:

image

图14

此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

因此,只要可以,请尽量在InnoDB上采用自增字段做主键。

后记

这篇文章断断续续写了半个月,主要内容就是上面这些了。不可否认,这篇文章在一定程度上有纸上谈兵之嫌,因为我本人对MySQL的使用属于菜鸟级别,更没有太多数据库调优的经验,在这里大谈数据库索引调优有点大言不惭。就当是我个人的一篇学习笔记了。

其实数据库索引调优是一项技术活,不能仅仅靠理论,因为实际情况千变万化,而且MySQL本身存在很复杂的机制,如查询优化策略和各种引擎的实现差异等都会使情况变得更加复杂。但同时这些理论是索引调优的基础,只有在明白理论的基础上,才能对调优策略进行合理推断并了解其背后的机制,然后结合实践中不断的实验和摸索,从而真正达到高效使用MySQL索引的目的。

另外,MySQL索引及其优化涵盖范围非常广,本文只是涉及到其中一部分。如与排序(ORDER BY)相关的索引优化及覆盖索引(Covering index)的话题本文并未涉及,同时除B-Tree索引外MySQL还根据不同引擎支持的哈希索引、全文索引等等本文也并未涉及。如果有机会,希望再对本文未涉及的部分进行补充吧。

参考文献

[1] Baron Scbwartz等 著,王小东等 译;高性能MySQL(High Performance MySQL);电子工业出版社,2010

[2] Michael Kofler 著,杨晓云等 译;MySQL5权威指南(The Definitive Guide to MySQL5);人民邮电出版社,2006

[3] 姜承尧 著;MySQL技术内幕-InnoDB存储引擎;机械工业出版社,2011

[4] D Comer, Ubiquitous B-tree; ACM Computing Surveys (CSUR), 1979

[5] Codd, E. F. (1970). “A relational model of data for large shared data banks”. Communications of the ACM, , Vol. 13, No. 6, pp. 377-387

[6] MySQL5.1参考手册 – http://dev.mysql.com/doc/refman/5.1/zh/index.html

Creative Commons License本文基于署名-非商业性使用 3.0许可协议发布,欢迎转载,演绎,但是必须保留本文的署名张洋(包含链接),且不得用于商业目的。如您有任何疑问或者授权方面的协商,请与我联系

 

Linux服务器性能评估

一、影响Linux服务器性能的因素
1. 操作系统级

  • CPU
  • 内存
  • 磁盘I/O带宽
  • 网络I/O带宽

2. 程序应用级

二、系统性能评估标准
影响性能因素

影响性能因素 评判标准
糟糕
CPU user% + sys%< 70% user% + sys%= 85% user% + sys% >=90%
内存 Swap In(si)=0

Swap Out(so)=0

Per CPU with 10 page/s More Swap In & Swap Out
磁盘 iowait % < 20% iowait % =35% iowait % >= 50%

 

其中:
%user:表示CPU处在用户模式下的时间百分比。
%sys:表示CPU处在系统模式下的时间百分比。
%iowait:表示CPU等待输入输出完成时间的百分比。
swap in:即si,表示虚拟内存的页导入,即从SWAP DISK交换到RAM
swap out:即so,表示虚拟内存的页导出,即从RAM交换到SWAP DISK。

三、系统性能分析工具

1.常用系统命令
Vmstat、sar、iostat、netstat、free、ps、top等

2.常用组合方式
• 用vmstat、sar、iostat检测是否是CPU瓶颈
• 用free、vmstat检测是否是内存瓶颈
• 用iostat检测是否是磁盘I/O瓶颈
• 用netstat检测是否是网络带宽瓶颈

四、Linux性能评估与优化

1. 系统整体性能评估(uptime命令)

[root@server ~]# uptime
16:38:00 up 118 days, 3:01, 5 users, load average: 1.22, 1.02, 0.91
这里需要注意的是:load average这个输出值,这三个值的大小一般不能大于系统CPU的个数,例如,本输出中系统有8个CPU,如果load average的三个值长期大于8时,说明CPU很繁忙,负载很高,可能会影响系统性能,但是偶尔大于8时,倒不用担心,一般不会影响系统性能。相反,如果load average的输出值小于CPU的个数,则表示CPU还有空闲的时间片,比如本例中的输出,CPU是非常空闲的。

2. CPU性能评估

(1)利用vmstat命令监控系统CPU
该命令可以显示关于系统各种资源之间相关性能的简要信息,这里我们主要用它来看CPU一个负载情况。
下面是vmstat命令在某个系统的输出结果:

[root@node1 ~]# vmstat 2 3
procs ———–memory———- —swap– —–io—- –system– —–cpu——
r b swpd free buff cache si so bi bo in cs us sy id wa st
0 0 0 162240 8304 67032 0 0 13 21 1007 23 0 1 98 0 0
0 0 0 162240 8304 67032 0 0 1 0 1010 20 0 1 100 0 0
0 0 0 162240 8304 67032 0 0 1 1 1009 18 0 1 99 0 0

  • Procs

r列表示运行和等待cpu时间片的进程数,这个值如果长期大于系统CPU的个数,说明CPU不足,需要增加CPU。
b列表示在等待资源的进程数,比如正在等待I/O、或者内存交换等。

  • Cpu

us列显示了用户进程消耗的CPU 时间百分比。us的值比较高时,说明用户进程消耗的cpu时间多,但是如果长期大于50%,就需要考虑优化程序或算法。
sy列显示了内核进程消耗的CPU时间百分比。Sy的值较高时,说明内核消耗的CPU资源很多。
根据经验,us+sy的参考值为80%,如果us+sy大于 80%说明可能存在CPU资源不足。

(2)利用sar命令监控系统CPU

sar功能很强大,可以对系统的每个方面进行单独的统计,但是使用sar命令会增加系统开销,不过这些开销是可以评估的,对系统的统计结果不会有很大影响。
下面是sar命令对某个系统的CPU统计输出:
[root@webserver ~]# sar -u 3 5
Linux 2.6.9-42.ELsmp (webserver) 11/28/2008 _i686_ (8 CPU)
11:41:24 AM CPU %user %nice %system %iowait %steal %idle
11:41:27 AM all 0.88 0.00 0.29 0.00 0.00 98.83
11:41:30 AM all 0.13 0.00 0.17 0.21 0.00 99.50
11:41:33 AM all 0.04 0.00 0.04 0.00 0.00 99.92
11:41:36 AM all 90.08 0.00 0.13 0.16 0.00 9.63
11:41:39 AM all 0.38 0.00 0.17 0.04 0.00 99.41
Average: all 0.34 0.00 0.16 0.05 0.00 99.45

对上面每项的输出解释如下:

  • %user列显示了用户进程消耗的CPU 时间百分比。
  • %nice列显示了运行正常进程所消耗的CPU 时间百分比。
  • %system列显示了系统进程消耗的CPU时间百分比。
  • %iowait列显示了IO等待所占用的CPU时间百分比
  • %steal列显示了在内存相对紧张的环境下pagein强制对不同的页面进行的steal操作 。
  • %idle列显示了CPU处在空闲状态的时间百分比。

问题
1.你是否遇到过系统CPU整体利用率不高,而应用缓慢的现象?
在一个多CPU的系统中,如果程序使用了单线程,会出现这么一个现象,CPU的整体使用率不高,但是系统应用却响应缓慢,这可能是由于程序使用单线程的原因,单线程只使用一个CPU,导致这个CPU占用率为100%,无法处理其它请求,而其它的CPU却闲置,这就导致了整体CPU使用率不高,而应用缓慢现象的发生。

3. 内存性能评估
(1)利用free指令监控内存
free是监控linux内存使用状况最常用的指令,看下面的一个输出:
[root@webserver ~]# free -m
total used free shared buffers cached
Mem: 8111 7185 926 0 243 6299
-/+ buffers/cache: 643 7468
Swap: 8189 0 8189
一般有这样一个经验公式:应用程序可用内存/系统物理内存>70%时,表示系统内存资源非常充足,不影响系统性能,应用程序可用内存/系统物理内存<20%时,表示系统内存资源紧缺,需要增加系统内存,20%<应用程序可用内存/系统物理内存<70%时,表示系统内存资源基本能满足应用需求,暂时不影响系统性能。

(2)利用vmstat命令监控内存

[root@node1 ~]# vmstat 2 3
procs ———–memory———- —swap– —–io—- –system– —–cpu——
r b swpd free buff cache si so bi bo in cs us sy id wa st
0 0 0 162240 8304 67032 0 0 13 21 1007 23 0 1 98 0 0
0 0 0 162240 8304 67032 0 0 1 0 1010 20 0 1 100 0 0
0 0 0 162240 8304 67032 0 0 1 1 1009 18 0 1 99 0 0

  • memory

swpd列表示切换到内存交换区的内存数量(以k为单位)。如果swpd的值不为0,或者比较大,只要si、so的值长期为0,这种情况下一般不用担心,不会影响系统性能。
free列表示当前空闲的物理内存数量(以k为单位)
buff列表示buffers cache的内存数量,一般对块设备的读写才需要缓冲。
cache列表示page cached的内存数量,一般作为文件系统cached,频繁访问的文件都会被cached,如果cache值较大,说明cached的文件数较多,如果此时IO中bi比较小,说明文件系统效率比较好。

  • swap

si列表示由磁盘调入内存,也就是内存进入内存交换区的数量。
so列表示由内存调入磁盘,也就是内存交换区进入内存的数量。
一般情况下,si、so的值都为0,如果si、so的值长期不为0,则表示系统内存不足。需要增加系统内存。

4.磁盘I/O性能评估
(1)磁盘存储基础

  • 熟悉RAID存储方式,可以根据应用的不同,选择不同的RAID方式。
  • 尽可能用内存的读写代替直接磁盘I/O,使频繁访问的文件或数据放入内存中进行操作处理,因为内存读写操作比直接磁盘读写的效率要高千倍。
  • 将经常进行读写的文件与长期不变的文件独立出来,分别放置到不同的磁盘设备上。
  • 对于写操作频繁的数据,可以考虑使用裸设备代替文件系统。

使用裸设备的优点有:

  • 数据可以直接读写,不需要经过操作系统级的缓存,节省了内存资源,避免了内存资源争用。
  • 避免了文件系统级的维护开销,比如文件系统需要维护超级块、I-node等。
  • 避免了操作系统的cache预读功能,减少了I/O请求。

使用裸设备的缺点是:

  • 数据管理、空间管理不灵活,需要很专业的人来操作。

(2)利用iostat评估磁盘性能
[root@webserver ~]# iostat -d 2 3
Linux 2.6.9-42.ELsmp (webserver) 12/01/2008 _i686_ (8 CPU)

Device: tps Blk_read/s Blk_wrtn/s Blk_read Blk_wrtn
sda 1.87 2.58 114.12 6479462 286537372

Device: tps Blk_read/s Blk_wrtn/s Blk_read Blk_wrtn
sda 0.00 0.00 0.00 0 0

Device: tps Blk_read/s Blk_wrtn/s Blk_read Blk_wrtn
sda 1.00 0.00 12.00 0 24
对上面每项的输出解释如下:

  • Blk_read/s表示每秒读取的数据块数。
  • Blk_wrtn/s表示每秒写入的数据块数。
  • Blk_read表示读取的所有块数。
  • Blk_wrtn表示写入的所有块数。
  1. 可以通过Blk_read/s和Blk_wrtn/s的值对磁盘的读写性能有一个基本的了解,如果Blk_wrtn/s值很大,表示磁盘的写操作很频繁,可以考虑优化磁盘或者优化程序,如果Blk_read/s值很大,表示磁盘直接读取操作很多,可以将读取的数据放入内存中进行操作。
  2. 对于这两个选项的值没有一个固定的大小,根据系统应用的不同,会有不同的值,但是有一个规则还是可以遵循的:长期的、超大的数据读写,肯定是不正常的,这种情况一定会影响系统性能。

(3)利用sar评估磁盘性能
通过“sar –d”组合,可以对系统的磁盘IO做一个基本的统计,请看下面的一个输出:
[root@webserver ~]# sar -d 2 3
Linux 2.6.9-42.ELsmp (webserver) 11/30/2008 _i686_ (8 CPU)

11:09:33 PM DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm %util
11:09:35 PM dev8-0 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

11:09:35 PM DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm %util
11:09:37 PM dev8-0 1.00 0.00 12.00 12.00 0.00 0.00 0.00 0.00

11:09:37 PM DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm %util
11:09:39 PM dev8-0 1.99 0.00 47.76 24.00 0.00 0.50 0.25 0.05

Average: DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm %util
Average: dev8-0 1.00 0.00 19.97 20.00 0.00 0.33 0.17 0.02
需要关注的几个参数含义:

  • await表示平均每次设备I/O操作的等待时间(以毫秒为单位)。
  • svctm表示平均每次设备I/O操作的服务时间(以毫秒为单位)。
  • %util表示一秒中有百分之几的时间用于I/O操作。

对以磁盘IO性能,一般有如下评判标准:
正常情况下svctm应该是小于await值的,而svctm的大小和磁盘性能有关,CPU、内存的负荷也会对svctm值造成影响,过多的请求也会间接的导致svctm值的增加。
await值的大小一般取决与svctm的值和I/O队列长度以及I/O请求模式,如果svctm的值与await很接近,表示几乎没有I/O等待,磁盘性能很好,如果await的值远高于svctm的值,则表示I/O队列等待太长,系统上运行的应用程序将变慢,此时可以通过更换更快的硬盘来解决问题。
%util项的值也是衡量磁盘I/O的一个重要指标,如果%util接近100%,表示磁盘产生的I/O请求太多,I/O系统已经满负荷的在工作,该磁盘可能存在瓶颈。长期下去,势必影响系统的性能,可以通过优化程序或者通过更换更高、更快的磁盘来解决此问题。

5. 网络性能评估

(1)通过ping命令检测网络的连通性
(2)通过netstat –i组合检测网络接口状况
(3)通过netstat –r组合检测系统的路由表信息
(4)通过sar –n组合显示系统的网络运行状态

 

转载自 http://www.itlearner.com/article/4553

转:MySQL数据库存储引擎和分支现状

在MySQL经历了2008年Sun的收购和2009年Oracle收购Sun的过程中,基本处于停滞发展的情况,在可以预见的未来,MySQL是肯定会被Oracle搁置并且逐步雪藏消灭掉的。MySQL随着相应的各主创和内部开发人员的离去,缔造了各个不同的引擎和分支,让MySQL有希望继续发扬光大起来。

本文大致讲解一下MySQL目前除了主要的 MyISAM、InnoDB、Heap(Memory)、NDB 等引擎之外的其他引擎的发展和现状,以及MySQL主干以外的分支的状况,为了我们未来更好的使用MySQL或者其他分支建立一个了解基础。

要了解主要存储引擎,请参考手册:http://dev.mysql.com/doc/refman/5.1/zh/index.html
或者相关介绍文章:http://www.javaeye.com/topic/211951

【MySQL存储引擎介绍】

[ Falcon存储引擎 ]

Falcon存储引擎是MySQL当时寄以厚望的存储引擎,主要是为了面对当时Oracle收购了InnoBase公司的情况,用来取代InnoDB的一个存储引擎。Falcon引擎的主导人员是数据库大师Jim Starkey,从2006年开始开发,到2008年发布Beta版本,至今为止也没有走入主流。2008年中旬,Falcon的主架构师Jim Starkey宣布从MySQL公司辞职,加入了一家创业公司NimbusDB担任CEO,去设计和开发运行在云计算上面的关系/语义数据库,按照2010年目前NoSQL市场的发展来看,他的选择是正确的,但是带来的结果是Falcon陷入一个没有主导人员的地步,导致了至今都属于性能糟糕,半死不活的状态。

Falcon引擎是MySQL AB公司基于Netfrastrucure公司的产品开发的(Netfrastrucure公司被MySQL AB收购),Falcon 当初的目标是嵌入到MySQL 6.0中用来取代InnoDB引擎,基本很多功能设计都是按照InnoDB的目标去设计的。

Falcon是面向多CPU、拥有大量内存的当代硬件环境和典型Web应用的数据库操作特点而开发的,主要功能包括多版本并发控制、完善的ACID支持、支持前缀压缩的B+树索引、数据页压缩(在磁盘上以压缩形式存储,在内存中以非压缩形式存储)、成组提交等。从功能方面来说没有什么新鲜事,大体也就实现了一个事务型存储引擎必须要有的功能(很多高级的功能如多表空间、分区等都还没有),但其架构上却有很多独特之处。

通过网上的一些测试结果Falcon的性能还是很糟糕的,写入速度是 MyISAM 的 1/10 ~ 1/20,Select 的优化也有问题,添加了索引感觉还会进行全表扫描。所以,我终究感觉 Falcon 是个杯具的引擎。

Falcon特性:http://dev.mysql.com/doc/falcon/en/se-falcon-features.html
Falcon测试:http://blog.gslin.org/archives/2008/02/12/1425/
Falcon手册:http://dev.mysql.com/doc/falcon/en/

[ SolidDB存储引擎]

solidDB存储引擎是由Solid Information Technology(http://www.soliddb.com) 开发的,这是一款利用MVCC来实现的事务型存储引擎。它既同时支持悲观和乐观并发控制,这一点其他的存储引擎目前都不支持。solibDB的MySQL版本包括对外键的完全支持。它在许多方面与InnoDB很相似,比如它使用了簇索引。solidDB还包括一个没有额外开销的在线备份功能。

solidDB公司已经由2008年被IBM收购,主要是用于整合为IBM数据库整合方案的一部分,目前是作为一个前端数据缓存的这么一个角色存在。IBM收购solidDB公司,主要是因为甲骨文在2005年6月收购了Solid Information Technology主要竞争对手TimesTen,为了在内存数据库这块市场上有所依托,所以收购了 solidDB公司。

solidDB产品是一个完整的打包程序,包括solidDB存储引擎、MyISAM存储引擎以及MySQL服务器。solidDB与MySQL之间的结合出现于2006年的晚些时候。但是底层的技术以及代码却是经过了该公司15年的完善。Solid公司保证和支持了整个产品。它是基于GPL协议的,并且提供了一个类似于MySQL服务器形式的商业版本。
性能上来说,SolidDB for MySQL开源数据库再次被证明能够完全满足高吞吐量、关键任务级应用对系统性能和可扩展性的要求。

但是就 solidDB被IBM收购,MySQL对Oracle收购的情况来看,基本上 solidDB for MySQL 是一个没法继续被MySQL使用的引擎,所以也是一个杯具的MySQL引擎。

官方网站:http://www.ibm.com/software/data/soliddb/

[ XtraDB存储引擎 ]

XtraDB存储引擎是percona公司对于innodb存储引擎进行改进加强后的产品,第一个版本发布于2008年底。XtraDB兼容innodb的所有特性,并且在IO性能,锁性能,内存管理等多个方面进行了增强。

Percona是一个MySQL技术咨询公司,他们有一个在MySQL领域很有名的技术博客叫做 Mysql Performance Blog,同时他们编写了一本很有名的MySQL书叫做《High Performance MySQL》,目前也出版了中文版。他们公司还有一个很有名的MySQL备份工具叫做 XtraBackup。

XtraDB的设计目标也是取代InnoDB作为目标,它是基于InnoDB来做的开发,XtraDB 100%的兼容 InnoDB,通常可以认为 XtraDB 是 InnoDB的升级或者替代版本。在性能上来说,目前 XtraDB 是非常高的,在大部分情况下也是比较稳定的,值得你尝试使用。同样XtraDB也是未来感觉很有前途的一个存储引擎,值得我们期待。

性能测试:http://www.mysqlperformanceblog.com/2009/07/14/performance-improvements-in-percona-5-0-83-and-xtradb/
使用情况:http://www.ningoo.net/html/2009/xtradb_storage_engine.html

引擎介绍:http://www.percona.com/docs/wiki/percona-xtradb:start
引擎下载:http://www.percona.com/percona-builds/Percona-XtraDB/
公司官网:http://www.percona.com
性能博客:http://www.mysqlperformanceblog.com

[ Maria存储引擎 ]

Maria由MySQL的创始人,MyISAM的作者Monty (Michael Widenius) 开发,命名为Maria是因为他的第三个小孩就叫Maria。Maria是Monty在MySQL公司的时候就开始开发的一个MySQL的分支引擎,Sun收购MySQL后,因为与Sun针对MySQL团队的一些问题不和,然后在2009年初离开了Sun,成立了 Monty Program Ab 公司,专门用于针对 Maria 引擎的开发,同时开发了一个MySQL的分支,叫做 MariaDB。

Maria是一个MySQL的存储引擎,利用它来扩展MyISAM使之在异常退出时文件不至于损坏。Maria的主要目的是作为更好的MyISAM,提供崩溃后的故障恢复功能。更长远的目标是成为一个全功能的事务型存储引擎,支持ACID、回滚、多版本并发控制、行级锁、成组提交,同时也可以选择不支持事务,最终代替MyISAM成为MySQL的默认存储引擎。

目前Maria引擎有针对MySQL 5.1 的版本,基本上就是一个增加了崩溃恢复功能的MyISAM,使用表级锁,但可以做到读写不冲突,即在进行任何类型的更新操作的同时都可以进行读操作,但多个写操作不能并发。

Maria的特点:
1. 多版本并发控制,ACID支持
2. 通过拷贝日志就能进行增强备份
3. 高效的磁盘存储

Maria 引擎开发之初就是用来取代MyISAM的存储引擎,并且目前按照我了解有些在使用公司的情况,运行情况挺不错,大家也可以尝试一下。Maria 在目前有MySQL创始人带领的情况下,也是一个非常有前途的的存储引擎,值得期待。

Maria下载:http://askmonty.org/wiki/MariaDB:Download
Maria手册:http://askmonty.org/wiki/Maria

[ PrimeBase XT (PBXT) 存储引擎 ]

PBXT 是 PrimeBase 公司推出的MySQL插件引擎,其功能和 InnoDB 类似,它是一款事务型存储引擎,并且它的设计是很独特的。它的一个很与众不同的特征就是如何来使用事务日志和数据文件来防止“write-ahead”日志,这可以极大的减少事务提交的开销。这个架构给了PBXT很大的提高写并发的空间,并且测试也表明它在某些特定的操作下比InnoDB要快。PBXT也使用了MVCC并且支持外键约束,但是它不使用簇索引。

主要特性如下:

MVCC的 :多版本并发控制,使读操作没有锁定
事务性 :支持启动开始,COMMIT和ROLLBACK和恢复上
ACID标准 :原子性,一致性,隔离,持久(一次提交的更改不能丢失)
行级锁定 :更新使用行级锁的并发允许最大并发量
死锁检测 :立即通知如果客户端进程已陷入死锁
参照完整性 :外键的支持。
写一次 :PBXT避免的架构双写入使用日志。
BLOB的流 :在结合的 BLOB Streaming engine.。 (http://www.blobstreaming.org/)

按照有人的测试结果来看,PBXT存储引擎版本的TPS随着线程数的增长,表现比较稳定,性能上与innodb差不多,长期来看,它的目标也是作为一个能够取代InnoDB的存储引擎。而且目前 MariaDB 这个分支已经把 PBXT 作为内置的存储引擎,所以也是可以尝试使用的一个引擎。

性能测试:http://imysql.cn/2008_07_25_innodb_vs_pbxt
引擎下载:http://www.primebase.org/download/index.php
官方网站:http://www.primebase.org/

【MySQL分支介绍】

[ MariaDB 数据库]

MariaDB 是一个采用 Maria 存储引擎的 MySQL 分支版本,是由原来 MySQL 的作者 Michael Widenius (Monty) 创办的Monty Program Ab公司所开发的免费开源的数据库服务器。基本上 MariaDB 的历史跟我上面讲的 Maria 存储引擎历史一样。MariaDB的设计目标就是用来取代 MySQL Server。Monty是开源数据库联盟(Open Database Alliance)的发起者,所以 MariaDB 也是开源数据库联盟的成员。

MariaDB基于事务的Maria存储引擎,替换了MySQL的MyISAM存储引擎,它使用了Percona的 XtraDB引擎来替换InnoDB,MariaDB的存储引擎还包括了 PrimeBase XT (PBXT) 和 FederatedX 存储引擎,MariaDB基于GPL 2.0发布。

Monty Widenius提供了MySQL的分支MariaDB候选版本。MariaDB 5.1完全兼容MySQL 5.1,这个版本早在2008年11月就发布了,增加了很多新的功能和若干个新的补丁程序。开发者称这个候选版本非常稳定。基本上 MySQL,MariaDB 解决了很多问题,例如“pool of threads”功能提供解决多数据连接问题。目前 MariaDB 发布的Release版本是 5.1.44,基本上应该是跟 MySQL 5.1 的版本兼容的。

MariaDB 基本上名门之后,加上MySQL创始人Monty的实力和号召力,是作为MySQL一个非常好的替代品,前途发展无限,值得我们尝试使用。

MariaDB中存储引擎介绍:
Maria: http://askmonty.org/wiki/Maria
XtraDB: http://www.percona.com/docs/wiki/percona-xtradb:start
PBXT: http://www.primebase.org/
FederatedX: https://launchpad.net/federatedx

MariaDB下载:http://askmonty.org/wiki/MariaDB:Download
MariaDB网站:http://askmonty.org

[ Drizzle 数据库]

Drizzle,是从MySQL衍生出来的一个数据库服务器,一个精简版的MySQL分支,Drizzle项目的宗旨是构建一个“更精练、更轻量、更快速”的MySQL版本,它的扩展性和易用性与MySQL相当,但为了提高性能和扩展性,它从原来的核心系统里移除了部分功能。 Drizzle 也是开源数据库联盟(Open Database Alliance)成员。

MySql的架构设计总监Brian Aker在O’Reilly开放源码大会(OSCON)上对Drizzle做了介绍。Drizzle是一个能为某些特定类别的应用提供支持的数据库项目(“what if” project)。Drizzle的设计目标:
1. Web应用。
2. 云计算组件。
3. 没有业务逻辑的数据库(又名存储过程)。
4. 多核架构。

Drizzle,一个精简版的MySQL分支,在目前的MySQL代码基本之上,将存储过程、视图、触发器、查询缓存、PREPARE语句等等没什么必要 的功能从代码中删掉,简化对数据类型和存储引擎的支持,并且进行大胆的重构。最终要实现的目的是将MySQL的代码大大简化,理顺MySQL的架构,改善 MySQL的代码质量,提高系统的稳定性和性能。将更适合 Web应用、云计算组件、没有业务逻辑的数据库(又名存储过程)、多核架构 等业务

Drizzle的特征有:
* 基于MySQL 6.0的源码树
* 无附加库
* 遵守POSIX
* 微内核设计
* 可插拔架构,适用于视图、存储过程、UDF、存储引擎等
* 跨多个节点的Sharding技术
* 智能代理
* 多CPU/多核CPU
* 优化的字段类型
* 高效的内存使用
* 没有内部ACL,使用LDAP/PAM
* 没有数据库数据格式化
* 整理有序的Make系统
* 缺省存储引擎为InnoDB
* 移除Windows兼容性

Drizzle 缺省的存储引擎是InnoDB,支持的数据类型更少,基本上设计目标跟 MariaDB 完全不同。MariaDB的设计目标是一个取代MySQL的数据库,而 Drizzle 基本上是一个除了MySQL之外你可以选择的产品,并且基本上设计目标是针对未来的云计算和分布式Web存储的方向去的,目前可能不是太稳定,不适合在运营环境使用,但是相当的值得期待。

Drizzle使用:http://database.51cto.com/art/200907/137239.htm
Drizzle下载:https://launchpad.net/drizzle
Drizzle网站:http://drizzle.org/

【总结语】

基本上来说,目前MySQL还是主流(MyISAM/InnoDB),但是未来发展不可预测,并且有这些除了MySQL之外的选择,也许有一天Oracle把MySQL彻底消灭掉了,但是我们同样还有 MariaDB、Drizzle可以选择,这就是开源的力量。

对比几个MySQL的存储引擎,Maria 和 XtraDB 是值得大家目前投入逐步使用的行列的,多做一些测试,灰度放亮,获得一个合理结果然后再使用是比较合适的。MySQL的数据库分支来说,MariaDB 也是比较值得尝试使用的,毕竟目前 Drizzle 还不是太成熟稳定,并且不一定适合你所做的业务。我所了解国内部分互联网公司也有在使用 MariaDB 的,并且效果不错,大家也都可以按照自己的情况来使用。

目前NoSQL运动如火如荼,有些业务更适合采用Key==>Value或这是BigTable类型的数据存储方式,也许MySQL不是最好的,当然选择最合适存储,也许未来大部分数据库市场会被NoSQL所占领,但是我觉得关系型数据库还是未来几年很重要的存储方式。

在MySQL被Sun收购,已经Sun被Oracle收购的过程中,整个开源世界都是在翻天覆地的变化,特别是MySQL的命运一直都是所有使用和热爱开源数据库的人们所关注的,在这些商业竞争中,那些开源斗士(比如 Monty),都通过别的方式,继续发扬了MySQL这种开源数据库。我们长期来看,总会有一些东西会消失,比如 Falcon存储引擎,有些东西会继续发展,比如 MariaDB或Drizzle,但是这些都为开源技术做出了贡献,也为数据库领域增添了色彩。

附:本文参考了一些文档,没法一一列出,非常感谢文档的作者和网站。:-)

来源:http://blog.csdn.net/heiyeshuwu/archive/2010/04/13/5481165.aspx

转:免费电子书列表

原帖的地址在stackoverflow.com

List of Free Programming books (compiled):

Graphics Programming

Language Agnostic

ASP.NET MVC:

Assembly Language

Bash

C/C++

C#

  • See .NET below

Django

Forth

Git

Haskell

Java

JavaScript

Linux

Lisp

Lua

Maven

Mercurial

.NET (C#)

NoSQL

Objective-C

Parrot / Perl 6

Perl

PHP

PowerShell

Prolog

PostgreSQL

Python

Ruby

Scala

Scheme

SmallTalk

Subversion

*SQL (Implementation agnostic) *

Vim

转:netty 中文手册

原文地址:http://docs.jboss.org/netty/3.1/guide/html_single/

The Netty Project 3.1 User Guide
The Proven Approach to Rapid Network Application Development

3.1.5.GA, r1772

序言
1. 问题
2. 方案 

第一章. 开始
1.1. 开始之前
1.2. 抛弃协议服务
1.3. 查看接收到的数据
1.4. 响应协议服务
1.5. 时间协议服务
1.6. 时间协议服务客户端 
1.7. 流数据的传输处理   
1.7.1. Socket Buffer的缺陷  
1.7.2. 第一种方案 
1.7.3. 第二种方案
1.8. 使用POJO代替ChannelBuffer
1.9. 关闭你的应用
1.10. 总述 

第二章. 架构总览
2.1. 丰富的缓冲实现 
2.2. 统一的异步 I/O API 
2.3. 基于拦截链模式的事件模型 
2.4. 适用快速开发的高级组件
2.4.1. Codec框架
2.4.2. SSL / TLS 支持 
2.4.3. HTTP实现
2.4.4. Google Protocol Buffer 整合 
2.5. 总述 

序言
本指南对Netty 进行了介绍并指出其意义所在。

1. 问题
现在,我们使用适合一般用途的应用或组件来和彼此通信。例如,我们常常使用一个HTTP客户端从远程服务器获取信息或者通过web services进行远程方法的调用。

然而,一个适合普通目的的协议或其实现并不具备其规模上的扩展性。例如,我们无法使用一个普通的HTTP服务器进行大型文件,电邮信息的交互,或者处理金 融信息和多人游戏数据那种要求准实时消息传递的应用场景。因此,这些都要求使用一个适用于特殊目的并经过高度优化的协议实现。例如,你可能想要实现一个对 基于AJAX的聊天应用,媒体流或大文件传输进行过特殊优化的HTTP服务器。你甚至可能想去设计和实现一个全新的,特定于你的需求的通信协议。

另一种无法避免的场景是你可能不得不使用一种专有的协议和原有系统交互。在这种情况下,你需要考虑的是如何能够快速的开发出这个协议的实现并且同时还没有牺牲最终应用的性能和稳定性。

2. 方案
Netty 是一个异步的,事件驱动的网络编程框架和工具,使用Netty 可以快速开发出可维护的,高性能、高扩展能力的协议服务及其客户端应用。

也就是说,Netty 是一个基于NIO的客户,服务器端编程框架,使用Netty 可以确保你快速和简单的开发出一个网络应用,例如实现了某种协议的客户,服务端应用。Netty相当简化和流线化了网络应用的编程开发过程,例如,TCP和UDP的socket服务开发。

“快速”和“简单”并不意味着会让你的最终应用产生维护性或性能上的问题。Netty 是一个吸收了多种协议的实现经验,这些协议包括FTP,SMPT,HTTP,各种二进制,文本协议,并经过相当精心设计的项目,最终,Netty 成功的找到了一种方式,在保证易于开发的同时还保证了其应用的性能,稳定性和伸缩性。

一些用户可能找到了某些同样声称具有这些特性的编程框架,因此你们可能想问Netty 又有什么不一样的地方。这个问题的答案是Netty 项目的设计哲学。从创立之初,无论是在API还是在其实现上Netty 都致力于为你提供最为舒适的使用体验。虽然这并不是显而易见的,但你终将会认识到这种设计哲学将令你在阅读本指南和使用Netty 时变得更加得轻松和容易。

继续阅读“转:netty 中文手册”

转:用正则表达式检查素数

一般来说,我们会使用正规表达式来做字符串匹配,今天在网上浏览的时候,看到了有人用正则表达式来检查一个数字是否为素数(质数),让我非常感兴趣,这个正则表达式如下所示:

/^1?$|^(11+?)1+$/

要使用这个正规则表达式,你需要把自然数转成多个1的字符串,如:2 要写成 “11”, 3 要写成 “111”, 17 要写成“11111111111111111”,这种工作使用一些脚本语言可以轻松的完成。

一开始我对这个表达式持怀疑态度,但仔细研究了一下这个表达式,发现是非常合理的,下面,让我带你来细细剖析一下是这个表达式的工作原理。

首先,我们看到这个表达式中有“|”,也就是说这个表达式可以分成两个部分:/^1?$/ 和 /^(11+?)1+$/

* 第一部分:/^1?$/, 这个部分相信不用我多说了,其表示匹配“非空串”以及字串中不只一个“1”的字符串。
* 第二部分:/^(11+?)1+$/,这个部分是整个表达式的关键部分。其可以分成两个部分,(11+?) 和1+$,前半部很简单了,匹配以“11”开头的并重复0或n个1的字符串,后面的部分意思是把前半部分作为一个字串去匹配还剩下的字符串1次或多次(这句话的意思是——剩余的字串的1的个数要是前面字串1个数的整数倍)。

通过上面的分析,我们知道,第二部分是最重要的,对于第二部分,举几个例子,

示例一:判断自然数8。我们可以知道,8转成我们的格式就是“11111111”,对于(11+?),其匹配了“11”,于是还剩下“111111”,而1+$正好匹配了剩下的“111111”,因为,“11”这个模式在“111111”出现了三次,符合模式匹配,返回true。取反(^),所以,得到false,于是这个数不是质数。

示例二:判断自然数11。转成我们需要的格式是“11111111111”(十一个1),对于(11+?),其匹配了“11”(前两个1),还剩下“111111111”(九个1),而1+$无法为“11”匹配那“九个 1”,因为“11”这个模式并没有在“九个1”这个串中正好出现N次。于是,我们的正则表达式引擎会尝试下一种方法,先匹配“111”(前三个1),然后把“111”作为模式去匹配剩下的“11111111”(八个1),很明显,那“八个1”并没有匹配“三个1”多次。所以,引擎会继续向下尝试……直至返回false。

通过示例二,我们可以得到这样的等价数算算法,正则表达式会匹配这若干个1中有没有出现“二个1”的整数倍,“三个1”的整数倍,“四个1”的整数倍……,而,这正好是我们需要的算素数的算法。现在大家明白了吧。

下面,我们用perl来使用这个正规则表达式不停地输出素数:(关于perl的语法我就不多说了)

perl -e’$|++;(1 x$_)!~/^1?$|^(11+?)1+$/&&print”$_ “while ++$_’

另外,让我们来举一反三,根据上述的这种方法,我们甚至可以用正则表达式来求证某方式是否有解,如:

* 二元方程:17x + 12y = 51 判断其是否有解的正则表达式是:^(.*)1{16}(.*)2{11}$
* 三元方程:11x + 2y + 5z = 115 判断其是否有解的正则表达式是:^(.*)1{10}(.*)2{1}(.*)3{4}$

大家不妨自己做做练习,为什么上述的两个正则表达式可以判断方程是否有解。如果无法参透其中的奥妙的话,你可以读读这篇英文文章

转自 cool shell : http://coolshell.cn/?p=2704

翻译:Google VP8 Code 首次深入技术分析

翻译来自:唐福林 博客雨 http://blog.fulin.org/2010/05/vp8_first_in_depth_tech_analysis.html

注1:文章来自:http://x264dev.multimedia.cx/?p=377 ,一个 H264 开发者对 VP8 的深入分析。

注2:在Google翻译基础上试译,不足之处请多包涵,欢迎各种建议和意见

The first in-depth technical analysis of VP8

首次深入技术分析

Back in my original post about Internet video, I made some initial comments on the hope that VP8 would solve the problems of web video by providing a supposed patent-free video format with significantly better compression than the current options of Theora and Dirac.

在我原来写的关于互联网视频的博文中,我曾做了一些初步的设想,希望 VP8提供的免专利费的视频压缩视频格式,能显著的超过当前的选择 Theora 和 Dirac,解决当前互联网视频的难题。

Fortunately, it seems I was able to acquire access to the VP8 spec, software, and source a good few days before the official release and so was able to perform a detailed technical analysis in time for the official release.

幸运的是,在官方正式发布前几天,我似乎能够获得VP8规范,软件和源代码,因此能够在正式发布前对它做一个详细的技术分析。

The questions I will try to answer here are:

我会在这里尽量回答这些问题:

1. How good is VP8? Is the file format actually better than H.264 in terms of compression, and could a good VP8 encoder beat x264?

1。VP8有多好?在压缩比方面VP8文件格式真的比 H.264要好,一个好的VP8编码器可以击败x264吗?

On2 claimed 50% better than H.264, but On2 has always made absurd claims that they were never able to back up with results, so such a number is almost surely wrong.

On2公司声称VP8超过H.264标准  50%,但On2公司经常发表荒谬的声明但却从来不能用事实来证明它,所以这样的数字几乎肯定是错误的。

VP7, for example, was claimed to be 15% better than H.264 while being much faster, but was in reality neither faster nor higher quality.

例如VP7,据称超过H.264标准 15%,而且快得多,但实际上既不快,也不是质量更高。

2. How good is On2’s VP8 implementation? Irrespective of how good the spec is, is the implementation good, or is this going to be just like VP3, where On2 releases an unusably bad implementation with the hope that the community will fix it for them?

2。On2公司的VP8的实现如何?先不论规范多么好,它的实现是否足够好,还是和曾经的VP3一样,On2公司发布了一个几乎不能使用的差劲实现,希望开发社区来帮助完善?

Let’s hope not; it took 6 years to fix Theora!

希望不会,修复Theora就已经花了6年的时间!

3. How likely is VP8 to actually be free of patents? Even if VP8 is worse than H.264, being patent-free is still a useful attribute for obvious reasons.

3。VP8的专利免费有多确定?即使VP8不如H.264,专利免费仍然是一个非常吸引人的属性。

But as noted in my previous post, merely being published by Google doesn’t guarantee that it is.

但正如我在前面的博文里提到的,Google 发布它并不能保证它是免费的。

Microsoft did similar a few years ago with the release of VC-1, which was claimed to be patent-free — but within mere months after release, a whole bunch of companies claimed patents on it and soon enough a patent pool was formed.

微软在几年前做了类似的事情,发布了VC-1,声称是免专利费的。 但仅仅过了几个月,一大堆的公司声称拥有关于它的专利,并很快成立了一个专利池。

We’ll start by going through the core features of VP8.

我们将首先浏览一遍VP8的核心特点。

We’ll primarily analyze them by comparing to existing video formats. Keep in mind that an encoder and a spec are two different things: it’s possible for good encoder to be written for a bad spec or vice versa! Hence why a really good MPEG-1 encoder can beat a horrific H.264 encoder.

我们主要分析它们的格式,跟现有的格式做比较。 记住,编码器和规范是两个不同的东西:可能存在根据差的规范写出好的编码器实现,也可能反过来!所以为什么一个很好的MPEG – 1编码器可以击败一个差劲的H.264编码器。

But first, a comment on the spec itself.

但首先,关于规范本身的评论。

The spec consists largely of C code copy-pasted from the VP8 source code — up to and including TODOs, “optimizations”, and even C-specific hacks, such as workarounds for the undefined behavior of signed right shift on negative numbers.

这个规范里存在大量的从 VP8 源代码里拷贝过来的C语言代码,甚至包括一些 TODO,“优化”,甚至一些只在C语言里存在的技巧,比如负数的带符号右移的替代方法。

In many places it is simply outright opaque. Copy-pasted C code is not a spec. I may have complained about the H.264 spec being overly verbose, but at least it’s precise.

在许多地方简直是彻头彻尾不透明。 复制粘贴的C代码不是规范。我可能抱怨过冗长的H.264规格,但至少它是精确的。

The VP8 spec, by comparison, is imprecise, unclear, and overly short, leaving many portions of the format very vaguely explained.

相比之下,VP8 的规范是不确切的,不明确,过于短,还留下许多关于格式的很含糊的解释。

Some parts even explicitly refuse to fully explain a particular feature, pointing to highly-optimized, nigh-impossible-to-understand reference code for an explanation.

有些地方甚至明确拒绝完全解释一个特定的功能,却给了一个高度优化,无法理解的参考代码实现作为解释。

There’s no way in hell anyone could write a decoder solely with this spec alone.

所以根本没有人可以根据本规范来单独的实现一个解码器。

Now that I’ve gotten that out of my system, let’s get back to VP8 itself.

现在我已经摆脱了它(指规范?译者注)了,让我们回到VP8本身。

To begin with, to get a general sense for where all this fits in, basically all modern video formats work via some variation on the following chain of steps:

首先,为了获得一个大概的印象,基本上所有的现代的视频格式,都包含以下步骤的工作:

Encode: Predict -> Transform + Quant -> Entropy Code -> Loopfilter

编码:预测 – > 变换 – > 熵编码 – > 回放过滤
Decode: Entropy Decode -> Predict -> Dequant + Inverse Transform -> Loopfilter

解码:熵解码 – > 预测 – > 逆变换 – > 回放过滤

If you’re looking to just get to the results and skip the gritty technical details, make sure to check out the “overall verdict” section and the “visual results” section. Or at least skip to the “summary for the lazy”.

如果你只是希望得到结果,跳过这些繁琐的技术细节,请直接跳到“整体判决”部分和“视觉效果”一节。或者至少跳到“总结”一节。

继续阅读“翻译:Google VP8 Code 首次深入技术分析”

转:一种语言/编码检测的复合方法

转自: http://blog.i5un.com/item/21

翻译自Mozilla的网站。
这篇论文讨论了组合三种不同的检测方法来实现自动字符集检测。
A composite approach to language/encoding detection)
Shanjian Li (shanjian@netscape.com)
Katsuhiko Momoi (momoi@netscape.com)
Netscape Communications Corp.

[ 注:这篇论文最初发表在19届国际Unicode会议(19th International Unicode Conference)(San Jose)。那以后,我们的实现经受住了时间和实际应用的检验,并且,我们还作了许多改进。一个主要的变化是我们现在使用正序列来检测单字节字符集,参见 4.7和4.7.1节。这篇论文写于通用字符集检测代码集成到Moailla主代码前(参见第8节)。自此以后,字符集检测代码被合并到了代码树中。如想 查看最新的实现,请在Mozilla的代码树中查看相应代码。作者 – 2002年11月25日。]

1.概要:

这篇论文提供三种自动检测的方法来判定无明显字符集声明的文档的编码。我们将分别讨论每种方法的优点和缺点,并且提供了一种复合后的,更有效的方法 来检测编码,这样,三种检测方法就可以互为补充。我们认为自动检测在使浏览器用户避免经常使用编码菜单手动选择编码上很有用,同时在编码菜单很少出现的情 况下,提供了更合理的处理方式。我们假设,文档转化到Unicode对用户是透明的。无论字符编码采用的是某种Unicode编码还是本地编码,用户仅需 知道字符最终显示是正确的就行。好的自动编码检测能有效的帮助用户处理大部分的编码事项,而无需用户手动参与。
2.背景:

自从进入计算机时代以来,人们创造了许多使用计算机数据表示的编码方案来表达不同的文字/字符集。随着全球化和Internet的发展,跨语言和区 域的信息交换越来越重要。但是现存的多种编码方案对此是一个屏障。Unicode提供了通用的编码解决方案,但是,迄今为止,各种各样的因素使它并没有代 替现存的区域编码方案。除了W3C和IETF建议使用UTF-8作为缺省编码,比如XML,XHTML,RDF。因此,现今的国际化软件不仅要处理 Unicode编码,还要处理其它多种不同的编码方式。

我们当前的工作是在开发Internet浏览器的环境中开展的。为了处理如今Web上使用不同编码的各种语言,我们做了许多努力。为了获取正确的显 示结果,浏览器需要利用HTTP服务器返回的编码信息,网页或者是最终用户通过选择编码菜单而得到的编码方式。此外,大部分用户没有能力手动的通过编码菜 单来进行操作。如果没有编码信息的话,网页有时就会显示为“垃圾”字符,用户就无法得到他们想要的信息。这最终会导致用户认为他们的浏览器有故障或有 Bug。

由于越来越多的Internet标准协议指定Unicode作为缺省的编码方式,网页将会不容置疑的转向使用Unicode来编码。好的通用自动检 测方法可以对这种转向提供重要的贡献,因为它们工作很自然,无需用户使用编码菜单。在这种情况下,渐进的转向将会以用户不易察觉的方式进行,这是由于,对 用户来说,网页总会显示正确,他们无需考虑使用编码菜单。这种平滑的转变将使编码对用户来说越来越不需要关注。自动检测在这种场景中将很关键。

继续阅读“转:一种语言/编码检测的复合方法”

音乐搜索的极致

12530 PC客户端 咪咕 (页面最下方有一个很不显眼的下载链接) 搜索 原本计划是今天上线内测,20号正是随资源库后台一起上线,其实昨晚就已经替换掉了正式服务器上原来的接口。正因为昨晚悄无声息的上线,原本已经下班走到 家门口的我们,又被电话叫回公司,来解决一个刚刚发现的bug。

音乐搜索,第一期还没有特别做歌词的搜索,只对歌手名,歌曲名,专辑名做优化,加上数据量本身就很小(一共才不到100万首歌),只好在查询上做文章。我们当前一共设置了十层查询 Query:

1。精确匹配:歌手,歌曲,专辑,不分词字段,去掉前后多余空格,精确匹配
2。过滤后的精确匹配:歌手,歌曲,专辑,过滤字段,去掉所有特殊字符,英文转成小写,精确匹配
3。拼音全量匹配:歌手,歌曲,专辑,拼音全量字段,去掉所有非英文字符,英文转成小写,精确匹配
4。同音纠错匹配:歌手,歌曲,专辑,拼音全量字段,只对含中文的搜索词使用,中文转拼音,英文转小写,去掉所有特殊字符,精确匹配
5。拼音首字母匹配:歌手,拼音首字母字段,中文转拼音首字母,英文转小写,去掉所有特殊字符,精确匹配
6。前缀匹配:歌手,歌曲,专辑,不分词字段,去掉前后多余空格,英文转小写,前缀匹配
7。分词Must匹配:歌手,歌曲,专辑,(歌词),分词字段,分词,词之间使用Must连接,分词匹配
8。分词Should匹配:歌手,歌曲,专辑,(歌词),分词字段,分词,词之间使用Should连接,分词匹配
9。合并分词匹配:歌手+歌曲+专辑 分词字段,分词,(当前使用 Should 连接),分词匹配
10。模糊匹配:歌手,歌曲,专辑,分词字段,去掉前后多余空格,英文转小写,模糊匹配, 包含中文时模糊度:0.65 全英文模糊度:0.85

其中模糊匹配还分了两级:

a 拼音纠错
b 模糊查询,包括中文模糊和英文模糊(模糊度不一样)

当前拼音模糊是使用组合的办法来实现的:

1。建索引的时候,拼音全量字段里建的是字段的准确拼音,包括多音字的组合
2。搜索的时候,将用户输入的关键词转成拼音,在拼音全量字段里搜
3。模糊的时候,将用户输入关键词转成的拼音,按照模糊规则:n-l 互换,zh-z, ch-c, sh-s 互换,an-ang, en-eng, in-ing, on-ong 互换,每次只换一个(当前只支持模糊度为1的拼音模糊查询),如果有多个可以替换的点,则返回的结果为一个数组组合,然后使用 精确匹配在拼音全量字段进行查询

还有一种做法:

首先定义个所谓的拼音标准化过程:
n->l,zh->z, ch->c, sh->s ,an->ang, en->eng, in->ing, on->ong 不是互换,而是单向替换。
将一个拼音串的所有可替换点都替换后,得到的一个串,称为标准化串。
1。建索引的时候,歌曲名,歌手名,专辑名各新增一个标准化串字段,按”,”分词(多音字),存储字段的拼音标准化串
2。搜索的时候,将用户输入的关键词转成拼音,在拼音全量里面搜索
3。模糊的时候,将用户输入关键词的拼音再转成标准化串,在标准化串字段里面搜索

优点:不同那么复杂的组合逻辑
缺点:无法控制模糊度

拼一个很大的 Query 去 Lucene 里面查询最大的问题就是,排序很难控制。不停的查看 Lucene Explain 出来的打分细节,再微调 Query 之间的 boost 权值,再查看打分细节,再微调。特别是分词命中这个 Query ,Lucene 分词命中的默认打分规则,总觉得不太满意。自己做了一个 Similarity 的子类来算分,可毕竟不是专业的,考虑的不够全面,解决了一个问题,副作用带来更多的问题。最后,还是不得不放弃这个方向的尝试。

拼一个大 Query 的一个意外收获就是,发现 Lucene 2.9.0 的一个 bug:LUCENE-1974,提到官方 JIRA 后,很快被确认,并修复了,并且我提交的 TestCase 也被将接纳到 Lucene 的测试用例集合中。可惜 2.9.1 出来前,我们还是不得不将项目切换回 2.4.1 , 以避免这个 bug。

现在使用的 IK 分词器,总觉得行为有些奇怪,又没有什么地方可以设置的。天龙八部,最多分词分出来“天”,“八”是我们不想要的,最长分词,又分不出“天龙”,真是郁闷。

因为 Query 太复杂,Lucene 自带的标红效果不是很令人满意,所以标红的部分也是完全自己做的。仿照 Query 的模式,定义了一系列的规则,如全量命中,拼音命中,分词命中等,记录下每种规则匹配到的区段,最后做一次归并就可以了。

关键词提示,即用户在搜索框里输入的同时,下拉一个提示列表。现在的做法是建了一个单独的关键词索引,用户输入的时候,使用前缀去匹配。中文的 Trie 树比英文复杂不少,所以最开始没有选它。但现在发现关键词索引太大了,Lucene 更新太慢,才后悔最初的选型失误。关键词里面需要保存词频的信息,搜索量的信息,所以以后的更新肯定也会不少。明天继续想办法解决这个问题。

做完这个项目以后,大约所有的搜索功能,都不会让我觉得害怕了吧。

原创,转载请著名出处:唐福林 博客雨 http://blog.fulin.org/2009/10/acme_of_music_search.html