整合营销服务商

电脑端+手机端+微信端=数据同步管理

免费咨询热线:

别再一知半解啦,索引其实就这么回事

别再一知半解啦,索引其实就这么回事

者 | Amazing10

责编 | 屠敏

头图 | CSDN 下载自视觉中国

本文为「业余码农」投稿

索引的概念基本所有人都会遇到过,就算没有了解过数据库中的索引,在生活中也不可避免的接触到。比方说书籍的目录,字典的查询页,图书馆的科目检索等等。其实这些都是一种索引,并且所起到的作用大同小异。

而对于数据库而言,只不过是将索引的概念抽象出来,让建立索引的过程更为灵活而自由,从而可以在不同的场景下优化数据库的查询效率。

索引在数据库的实际应用场景中十分普遍,数据库的优化也离不开对索引的优化。同时,索引相关的知识也是面试高频的考点之一,是应试者理论结合现实最为直接的体现。

因此,本文将从基础理论出发,介绍 MySQL 按照逻辑角度的索引分类和实现,通过数据结构的实现原理阐述不同结构对建立索引带来的优劣势,同时针对物理存储的方式对索引的组织特点和应用场景进行分析。最后根据不同的应用场景尽可能的探究如何建立起高性能的索引。文章结构如下:

概念

什么是索引?

索引似乎并没有十分明确的定义,更多的是一种定性的描述。简单来讲,索引就是一种将数据库中的记录按照特殊形式存储的数据结构。通过索引,能够显著地提高数据查询的效率,从而提升服务器的性能。

专业一点来说呢,索引是一个排好序的列表,在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址。在数据库十分庞大的时候,索引可以大大加快查询的速度,这是因为使用索引后可以不用扫描全表来定位某行的数据,而是先通过索引表找到该行数据对应的物理地址然后访问相应的数据。

说起索引,其实并不是 MySQL 数据库特有的机制,在关系型数据库中都会有类似不同的实现。这里我们也只是讨论 MySQL 数据库中的索引实现。

事实上,说是 MySQL 的索引其实并不准确。因为在 MySQL 中,索引是在存储引擎层而不是服务器层实现的。这意味着我们所讨论的索引准确来说是 InnoDB 引擎或 MyISAM 引擎或其它存储引擎所实现的。

所以索引即便是在 MySQL 中也没有统一的标准,不同存储引擎的所实现的索引工作方式也并不一样。不是所有的存储引擎都支持相同类型的索引,即便是多个引擎支持同一种类型的索引,其底层的实现也可能不同。

为什么需要索引

说了这么多,索引似乎就是给数据库添加了一个「目录页」,能够方便查询数据。但是索引的作用就仅此而已了吗,为什么需要大费周章的建立并优化索引?

说个题外话,我其实查字典从来都不喜欢查目录页,无论是查中文还是英文。因为觉得那样很慢,一个个找索引,效率很低。我习惯用的方式就是直接翻开字典,根据翻开的位置进行前后调整。比方说我想找「酱 JIANG」字,会先随机翻到一页,可能是「F」开头,在「J」前面,就往后翻一点;如果随机翻到「L」,那就往前翻一点。重复直至找到。

这大概就是类似于二分查找的方式,看起来好像是摆脱了索引的束缚,并且也能够获得比较高的查询效率。但是其实转念一想,在计算机的运行处理中,「一个个找索引」这个过程其实非常快,不能跟我们手动比对偏旁部首的效率相提并论。同时,为什么我可以直接翻开字典根据字母进行调整呢,这其实不就是因为我的脑子里存在一个大概的「索引表」,知道每个字母大概对应于字典的哪一个位置。虽然是模糊的,但却是真实存在的。(好不容易强行解释了一波...)

如此一来,可以看出索引的一大好处是如其概念中所提及的,使用索引后可以不用扫描全表来定位某行的数据,而是先通过索引表找到该行数据对应的物理地址然后访问相应的数据。这样的方式自然减少了服务器在响应时所需要对数据库扫描的数据量。

不仅如此,在执行数据库的范围查询时,若不使用索引,那么MySQL会先扫描数据库的所有行数据并从中筛选出目标范围内的行记录,将这些行记录进行排序并生成一张临时表,然后通过临时表返回用户查询的目标行记录。这个过程会涉及到临时表的建立和行记录的排序,当目标行记录较多的时候,会大大影响范围查询的效率。

所以当添加索引时,由于索引本身具有的顺序性,使得在进行范围查询时,所筛选出的行记录已经排好序,从而避免了再次排序和需要建立临时表的问题。

同时,由于索引底层实现的有序性,使得在进行数据查询时,能够避免在磁盘不同扇区的随机寻址。使用索引后能够通过磁盘预读使得在磁盘上对数据的访问大致呈顺序的寻址。这本质上是依据局部性原理所实现的。

局部性原理:当一个数据被用到时,其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间) ,因此对于具有局部性的程序来说,磁盘预读可以提高I/O效率。

磁盘预读要求每次都会预读的长度一般为页的整数倍。而且数据库系统将一个节点的大小设为等于一个页,这样每个节点只需要一次 I/O 就可以完全载入。这里的页是通过页式的内存管理所实现的,概念在这里简单提一嘴。

分页机制就是把内存地址空间分为若干个很小的固定大小的页,每一页的大小由内存决定。这样做是为了从虚拟地址映射到物理地址,提高内存和磁盘的利用率。

所以呢,总结一下。索引的存在具有很大的优势,主要表现为以下三点:

  • 索引大大减少了服务器需要扫描的数据量

  • 索引可以帮助服务器避免排序和临时表

  • 索引可以将随机 I/O 变成顺序 I/O

以上三点能够大大提高数据库查询的效率,优化服务器的性能。因此一般来说,为数据库添加高效的索引对数据库进行优化的重要工作之一。

不过,凡事都有两面性。索引的存在能够带来性能的提升,自然在其它方面也会付出额外的代价。

索引本身以表的形式存储,因此会占用额外的存储空间;

索引表的创建和维护需要时间成本,这个成本随着数据量增大而增大;

构建索引会降低数据的修改操作(删除,添加,修改)的效率,因为在修改数据表的同时还需要修改索引表;

所以对于非常小的表而言,使用索引的代价会大于直接进行全表扫描,这时候就并不一定非得使用索引了。没办法,成年人的世界总是这么的趋利避害。

逻辑分类

从逻辑的角度来对索引进行划分的话,可以分为单列索引、全文索引、组合索引和空间索引。其中单列索引又可分为主键索引、唯一索引和普通索引。这里的逻辑可以理解为从 SQL 语句的角度,或者是从数据库关系表的角度。下面就简单介绍这些索引的作用和用法,以及在修改表的时候如何添加索引。

主键索引

即主索引,根据主键建立索引,不允许重复,不允许空值;

主键:数据库表中一列或列组合(字段)的值,可唯一标识表中的每一行。

加速查询 + 列值唯一(不可以有)+ 表中只有一个

ALTER TABLE 'table_name' ADD PRIMARY KEY pk_index('col');

唯一索引

用来建立索引的列的值必须是唯一的,允许空值。唯一索引不允许表中任何两行具有相同的索引值。比方说,在 employee 表中职员的姓 name 上创建了唯一索引,那么就表示任何两个员工都不能同姓。

加速查询 + 列值唯一(可以有)

ALTER TABLE 'table_name' ADD UNIQUE index_name('col');

普通索引

用表中的普通列构建的索引,没有任何限制。

仅加速查询

ALTER TABLE 'table_name' ADD INDEX index_name('col');

全文索引

用大文本对象的列构建的索引

ALTER TABLE 'table_name' ADD FULLTEXT INDEX ft_index('col');

组合索引

用多个列组合构建的索引,这多个列中的值不允许有空值。

多列值组成一个索引,专门用于组合搜索,其效率大于索引合并。

ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3');

在对多列组合建立索引时,会遵循「最左前缀」原则。

最左前缀原则:顾名思义,就是最左优先,上例中我们创建了 (col1, col2, col3) 多列索引,相当于创建了 (col1) 单列索引,(col1, col2) 组合索引以及 (col1, col2, col3) 组合索引。

所以当我们在创建多列索引时,要根据业务场景,将 where 子句中使用最频繁的一列放在最左边。

空间索引

对空间数据类型的字段建立的索引,底层可通过 R 树实现。只不过使用较少,了解即可。

实现原理

我们知道,索引的底层本身就是通过数据结构来进行实现的。那么根据其底层的结构,常见的索引类型可分为哈希索引,BTree 索引,B+Tree 索引等。这里我们就主要来介绍这三种索引背后的实现机制。

哈希索引

顾名思义,哈希索引是通过哈希表实现的。哈希表的特点在之前的文章「九大数据结构」中已经详细介绍过。通过哈希表的键值之间的对应关系,能够在查询时精确匹配索引的所有列。哈希索引将所有的根据索引列计算出来的哈希码存储在索引中,同时将指向每个数据行的指针保存在哈希表中。

上图是通过哈希索引查询行数据的示意图,可以发现哈希索引同样会发生哈希冲突,并且是通过链地址法解决冲突的。当发送冲突时,还需要对链表进行遍历对比,才能够找到最终的结果。

在 MySQL 中,只有 Memory 存储引擎显式的支持哈希索引,而innodb是隐式支持哈希索引的。

这里的隐式支持是指,innodb引擎有一个特殊的功能 “自适应哈希索引”,当innodb注意到一些索引值被使用的非常频繁时,且符合哈希特点(如每次查询的列都一样),它会在内存中基于 B-Tree 索引之上再创建一个哈希索引。这样就让 BTree 索引也具有哈希索引的一些有点。这是一个完全自动的、内部的行为。

由于哈希结构的特殊性,其用于非常高的检索效率,通过哈希函数的映射可以一步到位。但是同样也是因为结构的特殊,导致哈希索引只适用于某些特定的场合。哈希索引的限制[1]:

  1. 不支持范围查询,比如 WHERE a > 5;只支持等值比较查询,包括=、IN 、<=>

  2. 无法被用来避免数据的排序操作;因为经过了哈希函数的映射过程,使得丢失了哈希前后的大小关系,从而无法按照索引值的顺序存储。

  3. 不支持部分索引列的匹配查找,因为哈希索引始终使用索引列的全部内容来计算哈希值。例如在数据列 (A, B) 上建立哈希索引,如果查询只有数据列 A,则无法使用该索引。

  4. 无法避免表扫描。因为当出现哈希冲突的时候,存储引擎必须遍历链表(拉链法)中所有的行指针,逐行进行比较,直到找到所有符合条件的行。

  5. 哈希冲突很多的情况下,其索引维护的代价很高,并且性能并不一定会比 BTree 索引高。

BTree 索引

BTree 实际上是一颗多叉平衡搜索树。从名字可以看出,BTree 首先是一颗多叉搜索树,这意味着它是具有顺序的;其次 BTree 还是平衡的,这意味着它的左右子树高度差小于等于1。

事实上一颗 BTree 需要满足以下几个条件:

每个叶子结点的高度都是一样的;

每个非叶子结点由 n-1 个 key 和 n 个指针 point 组成,其中 d<=n<=2d, key 和 point 相互间隔,结点两端一定是 key;

叶子结点指针都为 ;

非叶子结点的key都是 [key, data] 二元组,其中 key 表示作为索引的键,data 为键值所在行的数据;

一颗常见的BTree树见下图。

这是一颗三阶的BTree,可通过键值的大小排序进行数据的查询和检索,其中叶子节点的指针都为空,因此省略没画。从上图可以发现,BTree 的树形状相较于我们之前常见的二叉树等结构,更为扁平和矮胖。

之所以这样设计,还是跟磁盘读取的特点有关。我们知道在建立索引时,也是需要占据物理空间的。而实际上当数据量比较大的时候,索引文件的大小也十分吓人。考虑到一个表上可能有多个索引、组合索引、数据行占用更小等情况,索引文件的大小可能达到物理盘中数据的1/10,甚至可达到1/3。

这就意味着索引无法全部装入内存之中。当通过索引对数据进行访问时,不可避免的需要对磁盘进行读写访问。同时我们还知道,内存的读写速度是磁盘的几个数量级。因此在对索引结构进行设计时要尽可能的减少对磁盘的读写次数,也就是所谓的磁盘 I/O 次数。

这也就是索引会采用 BTree 这种扁平树结构的原因,树的层数越少,磁盘I/O的次数自然就越少。不仅如此,我们上面提到过磁盘预读的局部性原理。根据这个原理再加上页表机制,能够在进行磁盘读取的时候更大化的提升性能。

BTree 相较于其它的二叉树结构,对磁盘的 I/O 次数已经非常少了。但是在实际的数据库应用中仍有些问题无法解决。

一是无法定位到数据行。通过 BTree 可以根据主键的排序定位出主键的位置,但是由于数据表的记录有多个字段,仅仅定位到主键是不够,还需要定位到数据行。虽然这个问题可以通过在 BTree 的节点中存储数据行或者增加定位的字段,但是这种方式会使得 BTree 的深度大幅度提高,从而也导致 I/O 次数的提高。

二是无法处理范围查询。在实际的应用中,数据库范围查询的频率非常高,而 BTree 只能定位到一个索引位置。虽然可以通过先后查询范围的左右界获得,但是这样的操作实际上无法很好的利用磁盘预读的局部性原理,先后查询可能会造成通过预读取的物理地址离散,使得 I/O 的效率并不高。

三是当数据量一大时,BTree的高度依旧会变得很高,搜索效率还是会大幅度的下降。

问题总是推动改进的前提。基于以上的问题考虑,就出现了对 BTree 的优化版本,也就是 B+Tree。

B+Tree索引

B+Tree 一看就是在 BTree 的基础上做了改进,那么到底改变了什么呢。废话不多说,先上图。

上图实际上是一种带有顺序索引的 B+Tree,与最基本的 B+Tree 的区别就在于叶子节点是否通过指针相连。一般数据库中常用的结构都是这种带有顺序索引的 B+Tree。后文探讨的也都是带顺序索引的 B+Tree 结构。

对比 BTree 和 B+Tree,我们可以发现二者主要在以下三个方面上的不同:

  1. 非叶子节点只存储键值信息,不再存储数据。

  2. 所有叶子节点之间都有一个链指针,指向下一个叶子节点。

  3. 数据都存放在叶子节点中。

看着 B+Tree,像不像是一颗树与一个有序链表的结合体。因而其实 B+Tree 也就是带有树和链表的部分优势。树结构使得有序检索更为简单,I/O 次数更少;有序链表结构使得可以按照键值排序的次序遍历全部记录。

B+Tree 在作为索引结构时能够带来的好处有:

一,I/O 次数更少。这是因为上文也说过,BTree 的节点是存放在内存页中的。那么在相同的内存页大小(一般为4k)的情况下,B+Tree 能够存储更多的键值,那么整体树结构的高度就会更小,需要的 I/O 次数也就越小。

二,数据遍历更为方便。这个优势很明显是由有序链表带来的。通过叶子节点的链接,使得对所有数据的遍历只需要在线性的链表上完成,这就非常适合区间检索和范围查询。

三,查询性能更稳定。这自然是由于只在叶子节点存储数据,所以所有数据的查询都会到达叶子节点,同时叶子节点的高度都相同,因此理论上来说所有数据的查询速度都是一致的。

正是由于 B+Tree 优秀的结构特性,使得常用作索引的实现结构。在 MySQL 中,存储引擎 MyISAM 和 InnoDB 都分别以 B+Tree 实现了响应的索引设计。

物理存储

虽说 B+Tree 结构都可以用在 MyISAM 和 InnoDB,但是这二者对索引的在物理存储层次的实现方式却不相同。InnoDB 实现的是聚簇索引,而 MyISAM 实现的却是非聚簇索引。在介绍聚簇索引之前,我们需要先了解以下啥是佩奇,不对,是啥是「主键索引」和「辅助索引」。

其实概念很简单。我们刚刚不是在讲 B+Tree 的时候说过,树的非叶子节点只存储键值。没错就是这个键值,当这个键值是数据表的主键时,那么所建立的就是主键索引;当这个键值是其它字段的时候,就是辅助索引。因而可以得出,主键索引只能有一个,而辅助索引却可以有很多个。

聚簇索引和非聚簇索引的区别也就是根据其对应的主键索引和辅助索引的不同特点而实现的。

聚簇索引

说回聚簇索引。先丢个定义。

聚簇索引的主键索引的叶子结点存储的是键值对应的数据本身;辅助索引的叶子结点存储的是键值对应的数据的主键键值。

这句话的信息量挺大的。首先,分析第一句话,主键索引的叶子节点存储的是键值对应的数据本身。

我们知道,主键索引存储的键值就是主键。那么也就是说,聚簇索引的主键索引,在叶子节点中存储的是主键和主键对应的数据。数据和主键索引是存储在一起的,一起作为叶子节点的一部分。

然后,分析第二句话,辅助索引的叶子结点存储的是键值对应的数据的主键键值。

我们又知道,辅助索引存储的键值是非主键的字段。那就也就是说,通过辅助索引,可以找到非主键字段对应的数据行中的主键。

重点来了。当然主键索引和辅助索引一结合,能干啥呢。当直接采用主键进行检索时,可通过主键索引直接获得数据;而当采用非主键进行检索时,先需要通过辅助索引来获得主键,然后再通过这个主键在主键索引中找到对应的数据行。

举个例子吧。假设有这么一个数据表。

那么采用聚簇索引的存储方式,对应的主键索引为:(主键为ID)

对应的辅助索引为:(键值为Name,大概的意思):

所以当使用where ID=7这样的条件查找主键,则按照B+树的检索算法即可查找到对应的叶节点,之后获得行数据。对Name列进行条件搜索,则需要两个步骤:第一步在辅助索引B+树中检索Name,到达其叶子节点获取对应的主键。第二步使用主键在主键索引B+树种再执行一次B+树检索操作,最终到达叶子节点即可获取整行数据。

最后把以上过程整理总结一下,聚簇索引实际上的过程就分为以下两个过程。现在这个图应该能够看懂了吧。

非聚簇索引

学完了聚簇索引,非聚簇索引就简单多啦。同样,先上定义。

非聚簇索引的主键索引和辅助索引几乎是一样的,只是主索引不允许重复,不允许空值,他们的叶子结点都存储指向键值对应的数据的物理地址。

与聚簇索引来对比着看,上面的定义能够说明什么呢。首先,主键索引和辅助索引的叶子结点都存储着键值对应的数据的物理地址,这说明无论是主键索引还是辅助索引都能够通过直接获得数据,而不需要像聚簇索引那样在检索辅助索引时还得多绕一圈。

同时还说明一个点,叶子结点存储的是物理地址,那么表示数据实际上是存在另一个地方的,并不是存储在B+树的结点中。这说明非聚簇索引的数据表和索引表是分开存储的。

同样,对非聚簇索引的检索过程来个总结。

无论是主键索引还是辅助索引的检索过程,都只需要通过相应的 B+Tree 进行搜索即可获得数据对应的物理地址,然后经过依次磁盘 I/O 就可访问数据。

对比聚簇索引和非聚簇索引,可以发现二者最主要的区别就是在于是否在 B+Tree 的节点中存储数据,也就是数据和索引是否存储在一起。这个区别导致最大的问题就是聚簇索引的索引的顺序和数据本身的顺序是相同的,而非聚簇索引的顺序跟数据的顺序没有啥关系。

索引优化

介绍了这么多的索引,其实最终都是为了建立高性能的索引策略,对数据库中的索引进行优化。索引的优化有很多角度,针对特定的业务场景可采用不同的优化策略。这里考虑到文章篇幅,就不具体介绍,下次再出一篇专门讲索引优化的文章。简单列举一下在进行优化时可以考虑的几个方向:

1 独立的列。索引列不能是表达式的一部分,也不能是函数的参数。

2 前缀索引和索引选择性。这二者实际上是相互制约的关系,制约条件在于前缀的长度。一般应选择足够长的前缀以保证较高的选择性(保证查询效率),同时又不能太长以便节省空间。

3 尽量使用覆盖索引。覆盖索引是指一个索引包含所有需要查询的字段的值,这样在查询时只需要扫描索引而无须再去读取数据行,从而极大的提高性能。

4 使用索引扫描来做排序。要知道,扫描索引本身是很快的,在设计索引时,可尽可能的使用同一个索引既满足排序,又满足查找行数据。

最后,在建立索引时给几个小贴士:

1 优先使用自增key作为主键

2 记住最左前缀匹配原则

3 索引列不能参与计算

4 选择区分度高的列作索引

5 能扩展就不要新建索引

总结

索引的概念和原理是我们在了解和精通数据库过程中无法逃避的重点,而事实上建立高性能的索引对实际的应用场景也具有重要意义。本文的目的依旧是由浅入深的介绍索引这么个东西,从概念到实现再到最终的优化策略。

点到为止,学无止境。掌握了基本的理论和概念后,还需要在实际的服务器开发场景中针对具体的问题和服务进行索引优化方案的设计和使用。功力不够,仍需努力。

Reference

  • 高性能 MySQL,Baron Schwartz 等人著,电子工业出版社

公众号码海系列文章:

  • https://www.jianshu.com/p/9e9aca844c13

  • https://www.runoob.com/mysql/mysql-index.html

  • https://www.cnblogs.com/Aiapple/p/5693239.html

  • https://blog.csdn.net/tongdanping/article/details/79878302

  • https://www.cnblogs.com/igoodful/p/9361500.html

击上方关注,All in AI中国

作者:Leonard Fink

在我们之前的博文中,我们讨论了如何更新Dropbox搜索引擎,以将智能添加到用户的工作流程中,以及我们如何构建光学字符识别(OCR)管道。用户将从这些变化中看到的最具影响力的好处之一是,Dropbox Professional和Dropbox Business Advanced 和企业计划的用户可以使用我们描述为自动图像文本识别的系统在图像和PDF中搜索英文文本。

自动识别图像中的文本(包括包含图像的PDF)的潜在好处是巨大的。人们在Dropbox中存储了超过200亿个图像和PDF文件。在这些文件中,10%-20%是文档类收据和白板图像的照片,而不是文档本身。这些现在是自动图像文本识别的候选者。同样,这些PDF中有25%的文件是扫描文档,这些文档也是自动文本识别的候选对象。

从计算机视觉的角度来看,虽然文档和文档图像可能看起来与人类查看看非常相似,但计算机看到这些文件的方式有很大差异:文档可以被编入索引以供搜索,允许用户通过输入找到它文件中的一些单词。搜索索引系统的图像是不透明的,因为它只显示为像素集合。图像格式(如JPEG,PNG或GIF)通常不可索引,因为它们没有文本内容,而基于文本的文档格式(如TXT,DOCX或HTML)通常是可索引的。PDF文件介于这二者之间,因为它们可以包含文本和图像内容的混合。自动图像文本识别能够智能地区分所有这些文档,以对包含在其中的数据进行分类。

现在,当用户搜索出现在这些文件中的英文文本时,它会出现在搜索结果中。这篇文章描述了我们是如何构建这个特性的。

评估挑战

首先,我们着手衡量任务的规模,特别是试图了解我们必须处理的数据量。这不仅可以告知成本估算,还可以确认其有用性。更具体地说,我们想回答以下问题: ·我们应该处理哪些类型的文件? ·哪些文件可能具有"OCR-able"内容? ·对于像PDF这样的多页文档类型,我们需要处理多少页才能使其有用?

我们要处理的文件类型是那些当前没有可索引文本内容的文件。这包括没有文本数据的图像格式和PDF文件。但是,并非所有图像或PDF都包含文本。事实上,大多数只是没有任何文字的照片或插图。因此,一个关键的构建模块是一个机器学习模型,可以确定某个内容是否具有OCR能力,换句话说,它是否具有很有可能被我们的OCR系统识别的文本。这包括,例如,文档的扫描或照片,但不包括具有随机路牌的图像之类的东西。我们训练的模型是一个卷积神经网络,它在将输出转换成关于它是否可能具有文本内容的二元决策之前获取输入图像。

对于图像,最常见的图像类型是JPEG,我们发现大约9%的JPEG可能包含文本。对于PDF文件,情况稍微复杂一些,因为PDF文件可以包含多个页面,并且每个页面可以存在三个类别之一: ·页面具有已嵌入和可索引的文本 ·页面具有文本,但仅以图像的形式,因此当前不可索引 ·页面没有实质性的文本内容

我们希望略过第1类和第3类中的页面,并只关注第2类,因为这是我们可以提供好处的地方。事实证明,3类中的每类分布分别为69%、28%和3%。总体而言,我们的目标用户的JPEG数量大约是PDF的两倍,但每个PDF平均有8.8页,而PDF包含文本图像的可能性要高得多,所以就系统上的总体负载而言,PDF的贡献将超过JPEG的10倍!然而,事实证明,通过下面描述的简单分析,我们可以显著减少这个数字。

页面总数

一旦我们决定了文件类型并开发了每页上可以使用OCR内容的估计值,我们就希望对处理每个文件的方式保持战略性。某些PDF文档有很多页面,因此处理这些文件的成本更高。幸运的是,对于长文档,我们可以利用这样一个事实,即使索引几页也可能使文档更容易从搜索中访问。因此,我们查看了PDF样本中页面计数的分布情况,以确定每个文件最多可以索引多少页面。事实证明,一半的PDF只有1页,大约90%有10页或更少。因此,我们采用了10页的上限,也就是每个文档中的前10页。这意味着我们完全索引了近90%的文档,并且索引剩余文档的足够页面以使其可搜索。

自动图像文本识别系统组件

渲染

一旦我们开始在所有OCR文件上使用OCR提取文本的过程,我们意识到我们有两个选项来渲染嵌入在PDF文件中的图像数据:我们可以提取嵌入在文件中的所有光栅(即像素)图像对象单独流,或者我们可以将PDF的整个页面渲染为栅格图像数据。在对两者进行实验之后,我们选择了后者,因为我们已经为我们的文件预览功能提供了强大的大规模PDF渲染基础架构。使用此系统的一些好处包括:

  • 它可以自然地扩展到其他渲染或图像嵌入文件格式,如PowerPoint、PostScript和我们的预览基础架构支持的许多其他格式。
  • 实际渲染自然保留文本标记的顺序和文本在布局中的位置,考虑文档结构,从多图像布局中提取单独的图像时无法保证。

我们的预览基础架构中使用的服务器端渲染基于PDF,这是Chromium项目中的PDF渲染器,这是一个由Google启动的开源项目,是Chrome浏览器的基础。相同的软件也用于正文检测并确定文档是否是"仅限于图像",这有助于决定我们是否要应用OCR处理。

一旦开始渲染,每个文档的页面将被并行处理以降低延迟,根据我们上面的分析,以前10页为上限。我们渲染每个页面的分辨率填充2048×2048像素的矩形,保留纵横比。

文档图像分类

我们的OCR机器学习模型最初是为Dropbox文档扫描仪功能而构建的,目的是为了确定用户最近拍摄的(正常)照片是否可以建议他们"变成扫描"。这个分类器是使用线性分类器构建的在预先训练的ImageNet模型(GoogLeNet / Inception)的图像特征之上。它接受了从几个不同来源收集的数千张图像的训练,包括公共图像、用户捐赠的图像和一些Dropbox员工捐赠的图像。原始开发版本是使用Caffe构建的,之后该模型转换为TensorFlow,以与我们的其他部署保持一致。 在微调这个组件的性能时,我们学到了一个重要的教训:在开始时,分类器偶尔会产生误报(它认为包含文本的图像,但实际上没有),例如空白墙壁、天际线或开阔水域的图片。尽管它们看起来与人眼完全不同,但是分类器在所有这些图像中都看到了相似的东西:它们都具有平滑的背景和水平线条。通过迭代标记并将这种所谓的"难分样本(hard negatives)"添加到训练集中,我们显著提高了分类的精确度,有效地教授了分类器,即使这些图像具有文本文档的许多特征,它们也不包含实际文本。

角点检测

在图像中定位文档的角并定义其(大致)四边形是字符识别之前的另一个关键步骤。给定角的坐标,可以通过简单的几何变换来校正图像中的文档(制成直角矩形)。文档角点检测器组件使用另一个ImageNet深度卷积网络(Densenet-121)构建,其顶层由产生四角坐标的回归器替代。

用于训练该模型的测试数据仅使用数百个图像。四个或更多定义封闭文档边界多边形的2-D点形式的标签也由Mechanical Turk工作人员使用定制的用户界面(UI)绘制,并通过机器学习团队成员的注释进行扩充。通常,包含在训练图像中的文档的一个或多个角落位于图像边界之外,需要人类直觉来填充缺失的数据。

由于深度卷积网络被馈送按比例缩小的图像,因此四边形的原始预测位置的分辨率低于原始图像。为了提高精度,我们采用两步流程:

(1)获得初始的四边形

(2)在每个角落的较高分辨率补丁上运行另一个回归

从四边形的坐标,可以很容易地将图像校正为对齐的版本。

令牌提取

在我们之前的博客文章中描述了实际的光学字符识别系统,它提取文本标记(大致对应于单词)。它将来自角点检测步骤的校正后的图像作为输入,并生成令牌检测,其中包括令牌的边界框和每个令牌的文本。这些被排列成大致顺序的令牌列表并添加到搜索索引中。如果有多个页面,则每个页面上的标记列表将串联在一起以生成一个大列表。

把碎片拼在一起

要为所有符合条件的用户在所有可能可索引的文件上运行自动图像文本识别,我们需要一个可以摄取传入文件事件(例如,添加或编辑)并启动相关处理的系统。事实证明,这是Cape的一个自然用例,这是一种灵活的、大规模、低延迟的异步事件流处理框架,支持许多Dropbox功能。作为一般搜索索引框架的一部分,我们为OCR处理添加了一个新的Cape微服务工作者(称为"lambda")。

处理的前几个步骤利用了Dropbox的一般预览基础设施。这是一个可以有效地将二进制文件作为输入并返回此文件的转换的系统。例如,它可能需要一个PowerPoint文件并生成该PowerPoint文件的缩略图。该系统可通过插件进行扩展,这些插件对特定类型的文件进行操作并返回特定的转换。因此,添加新文件类型或转换很容易。最后,系统还有效地缓存转换,因此如果我们尝试两次生成相同PowerPoint文件的缩略图图像,那么昂贵的缩略图操作只会运行一次。

我们为此功能编写了几个预览插件,包括(数字对应于上面的系统图):

  1. 检查我们是否应该继续处理,具体取决于它是JPEG、GIF、TIFF还是没有嵌入文本的PDF,以及用户是否有资格使用该特性。
  2. 运行OCR能力分类器,该分类器确定给定图像是否具有文本。
  3. 在每张图像上运行文档角点检测器,以便我们对其进行纠正。
  4. 使用OCR引擎提取令牌。
  5. 将令牌列表添加到用户特定的搜索索引中。

稳健性

为了在远程调用期间出现瞬态/临时错误的情况下提高系统的稳健性,我们使用抖动指数退避重试远程调用,这是分布式系统中的最佳实践技术。例如,通过第二次和第三次重试,我们将PDF元数据提取的失败率降低了88%。

性能优化

当我们将管道的初始版本部署到一小部分流量进行测试时,我们发现机器学习模型(角点检测、方向检测、OCR等)的计算开销将需要一个庞大的集群,这会使该特性过于昂贵部署。此外,我们发现看到的流量大约是我们根据历史增长率估算的流量的2倍。

为了解决这个问题,我们首先提高了OCR机器学习模型的吞吐量,并假设增加吞吐量可以最大限度地减少我们需要的OCR集群的大小。

为了实现准确可控的基准测试,我们构建了专用的沙箱环境和命令行工具,使我们能够将输入数据发送到多个子服务,以分别测量每个子服务的吞吐量和延迟。我们用于基准测试的秒表日志是从实际实时流量中采样的,没有残留数据收集。

从配置参数开始,我们选择从外部进入性能优化。在处理受CPU限制的机器学习瓶颈时,有时可以通过简单的配置和库更改来实现大的性能提升;我们将在下面讨论几个例子。

第一个提升来自为jails中运行的代码选择正确的并发度:为了安全起见,我们运行大多数直接触及软件监狱中用户内容的代码,这些代码限制了可以运行的操作,隔离来自不同用户的内容以防止软件错误从破坏数据,并保护我们的基础设施免受恶意威胁向量。我们通常在一台机器上为每个核心部署一个jail,以实现最大的并发性,同时允许每个jail只运行单线程代码(即数据并行)。

然而,事实证明,我们用于预测像素中的字符的TensorFlow深度学习框架默认配置了多核支持。这意味着每个jail现在都运行多线程代码,这导致了大量的场景切换开销。因此,通过关闭TensorFlow中的多核支持,我们能够将吞吐量提高约3倍。

在这个修复之后,我们发现性能仍然太慢 - 甚至在我们的机器学习模型之前,请求就会出现瓶颈!一旦我们针对使用的CPU核心数量调整了预分配的jail和RPC服务器实例的数量,我们终于开始获得预期的吞吐量。通过在TensorFlow中启用矢量化AVX2指令,并通过TensorFlow XLA将模型和运行时预编译到C ++库中,我们得到了额外的显着提升。最后,我们对模型进行了基准测试,发现狭窄中间层上的2D卷积是热点,并通过在图表中手动展开它们来加速它们。

文档图像流水线的两个重要组成部分是角点检测和方向预测,两者都使用深度卷积神经网络实现。与我们之前使用过的Inception-Resnet-v2模型相比,我们发现Densenet-121的速度几乎快两倍,而且在预测文档角落位置方面的准确性稍差。为了确保我们没有在准确性上回归太多,我们进行了A/B测试以评估对可用性的实际影响,比较用户手动校正自动预测文档角落的频率。我们得出结论,差异可以忽略不计,并且性能的提升是值得的。

为未来的智能功能铺平道路

使文档图像可搜索是向更加深入理解文档结构和内容的第一步。有了这些信息,Dropbox可以帮助用户更好地整理文件,这是迈向更开明的工作方式的一步。

自动图像文本识别是Dropbox工程师处理的涉及计算机视觉和机器学习的大型项目类型的主要示例。

者:Jia-Xin

cnblogs.com/YangJiaXin/p/11153579.html

前言

  • 只有Innodb和myisam存储引擎能用全文索引(innodb支持全文索引是从mysql5.6开始的)
  • char、varchar、text类型字段能创建全文索引(fulltext index type)
  • 全文索引的基于关键词的,如何区分不同的关键词了,就要用到分词(stopword)
  • 英文单词用空格,逗号进行分词;中文分词不方便(一个句子不知道怎样区分不同的关键词)
  • 内置分词解析器ngram支持中文,日文,韩文(将句子分成固定数字的短语)
  • 当对表写入大量数据时,写入数据后再创建全文索引的速度更快(减少了维护索引的开销)
  • 全文索引的原理的倒排索引(一种数据结构),一般利用关联数组,在辅助表中存储单词与文档中所在位置的映射

使用

用MATCH() … AGAINST 方式来进行搜索

match()表示搜索的是那个列,against表示要搜索的是那个字符串

查看默认的分词(以这些词来区分不同的关键词);也可以自定义分词,以这些词来区分不同的关键词SELECT * FROM information_schema.INNODB_FT_DEFAULT_STOPWORD;

三种类型的全文搜索方式

natural language search(自然语言搜索)

通过MATCH AGAINST 传递某个特定的字符串来进行检,默认方式

boolean search(布尔搜索)

为检索的字符串增加操作符,如“+”表示必须包含,"-"不包含,"*" 表示通配符,即使传递的字符串较小或出现在停词中,也不会被过滤掉

query expansion search(查询扩展搜索)

搜索字符串用于执行自然语言搜索,然后,搜索返回的最相关行的单词被添加到搜索字符串,并且再次进行搜索,查询将返回来自第二个搜索的行

相关参数

配置相关参数

innodb_ft_min_token_size默认3,表示最小3个字符作为一个关键词,增大该值可减少全文索引的大小

innodb_ft_max_token_size默认84,表示最大84个字符作为一个关键词,限制该值可减少全文索引的大小

ngram_token_size默认2,表示2个字符作为内置分词解析器的一个关键词,如对“abcd”建立全文索引,关键词为'ab','bc','cd'

当使用ngram分词解析器时,innodb_ft_min_token_size和innodb_ft_max_token_size 无效

注意 这三个参数均不可动态修改,修改了这些参数,需重启MySQL服务,并重新建立全文索引

测试innodb引擎使用全文索引

准备

1、目标

  • 查询文章中是否含有某个关键词;一系列文章出现某个关键词的次数
  • 查询文章的标题是否含有某个关键词

2、设置以下参数减少磁盘IO压力

SET GLOBAL sync_binlog=100;
SET GLOBAL innodb_flush_log_at_trx_commit=2;

3、导入1kw 数据进行测试全文索引

该数据来源网上搜索

https://pan.baidu.com/s/1aaB1R3bkBGZRMEx0o6T61w 提取码:60l7

4、某个文章表 的结构

使用myloader 多线程导入测试数据

-- 先把测试数据进行解压
tar -zxf mydumper_dump_article.tar.gz
time myloader -u $user -p $passwd -S $socket -t 32 -d /datas/dump_article -v 3

5、导入数据后总数据量和数据文件、索引文件大小

SELECT COUNT(*) FROM `article`;
+----------+
| COUNT(*) |
+----------+
| 10000000 |
+----------+
1 row in set (7.85 sec)

SELECT     table_name,   CONCAT(FORMAT(SUM(data_length) / 1024 / 1024,2),'M') AS dbdata_size,   CONCAT(FORMAT(SUM(index_length) / 1024 / 1024,2),'M') AS dbindex_size,   CONCAT(FORMAT(SUM(data_length + index_length) / 1024 / 1024 / 1024,2),'G') AS `db_size(G)`,   AVG_ROW_LENGTH,table_rows,update_time FROM   information_schema.tables WHERE table_schema = DATABASE() and table_name='article';
+------------+-------------+--------------+------------+----------------+------------+---------------------+
| table_name | dbdata_size | dbindex_size | db_size(G) | AVG_ROW_LENGTH | table_rows | update_time         |
+------------+-------------+--------------+------------+----------------+------------+---------------------+
| article    | 3,710.00M   | 1,003.00M    | 4.60G      |            414 |    9388739 | 2019-07-05 15:31:37 |
+------------+-------------+--------------+------------+----------------+------------+---------------------+

使用默认方式创建全文索引

1、该表已有关键词字段(对文章内容的简述),并以“,”作为分词符

2、不建全文索引时搜索某个关键词

需要进行全表扫描

3、对关键词字段创建全文索引(以 , 作为分词)

my.cnf配置文件中设置innodb_ft_min_token_size,并重启MySQL服务(最小两个字符作为一个关键词,默认三个字符作为一个关键词)

[mysqld]
innodb_ft_min_token_size=2

3.1 设置自定义stopwords(即分词)

USE mysql;
CREATE TABLE my_stopwords(VALUE VARCHAR(30)) ENGINE = INNODB;
INSERT INTO my_stopwords(VALUE) VALUE (',');
SET GLOBAL innodb_ft_server_stopword_table = 'mysql/my_stopwords';

~

SHOW GLOBAL  VARIABLES WHERE Variable_name IN('innodb_ft_min_token_size','innodb_ft_server_stopword_table');
+---------------------------------+--------------------+
| Variable_name                   | Value              |
+---------------------------------+--------------------+
| innodb_ft_min_token_size        | 2                  |
| innodb_ft_server_stopword_table | mysql/my_stopwords |
+---------------------------------+--------------------+

3.2 创建全文索引

alter table article add fulltext index idx_full_keyword(keywords);
* [ ] Query OK, 0 rows affected, 1 warning (1 min 27.92 sec)
* [ ] Records: 0  Duplicates: 0  Warnings: 1

3.3 剩余磁盘空间需足够,原表4.6G,剩余5.7G磁盘,添加全文索引也会失败

3.4 利用创建的全文索引进行查询某个关键词出现的次数

查询响应时间有了很大的提升,只需0.05s;使用where keywords like '%时尚%' 需要7.56s。推荐阅读:MySQL性能优化实践(很全面,值得收藏)

3.5 如需同时完全匹配多个关键词,用布尔全文搜索

表示完全匹配 "三里屯,北京" 的记录数

select count(*) from article where match(keywords)  against('+三里屯,北京' in boolean mode);
+----------+
| count(*) |
+----------+
|        1 |
+----------+
1 row in set (0.06 sec)

表示匹配“三里屯” 或者 “北京”的记录数

select count(*) from article where match(keywords)  against('三里屯,北京');
+----------+
| count(*) |
+----------+
|        8 |
+----------+
1 row in set (0.06 sec)

3.6 创建全文索引后,会创建一些其它文件

96K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_1.ibd96K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_2.ibd96K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_3.ibd96K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_4.ibd128K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_5.ibd256K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_6.ibd96K Jul 5 16:29 FTS_00000000000000a7_BEING_DELETED_CACHE.ibd96K Jul 5 16:29 FTS_00000000000000a7_BEING_DELETED.ibd96K Jul 5 16:30 FTS_00000000000000a7_CONFIG.ibd96K Jul 5 16:29 FTS_00000000000000a7_DELETED_CACHE.ibd96K Jul 5 16:29 FTS_00000000000000a7_DELETED.ibd

  • 前6个表示倒排索引(辅助索引表)
  • 第7,8个表示包含已删除文档的文档ID(DOC_ID),其数据当前正在从全文索引中删除
  • 第9个表示FULLTEXT索引内部状态的信息
  • 第10,11个表示包含已删除但尚未从全文索引中删除其数据的文档

使用ngram分词解析器创建全文索引

1、对title字段建立全文索引(该字段没有固定的stopwords 分词,使用ngram分词解析器)

需先在my.cnf 配置文件中设置ngram_token_size(默认为2,2个字符作为ngram 的关键词),并重启mysql服务

这里使用默认的 2

select title from article limit 10;
+------------------------------------------------------------------------------+
| title                                                                        |
+------------------------------------------------------------------------------+
| worth IT                                                                    |
|Launchpad 江南皮革厂小show                                                  |
|Raw 幕后罕见一刻 “疯子”被抬回后台                                           |
|Raw:公子大骂老爸你就是个绿茶  公子以一打四                                  |
|四组30平米精装小户型,海量图片,附户型图                                    |
|夜店女王性感烟熏猫眼妆                                                      |
|大秀哥重摔“巨石”强森                                                        |
|少女时代 崔秀英 服饰科普 林允儿 黄美英 金泰妍 郑秀晶                        |                                              
|德阳户外踏青,花田自助烧烤                                                  |
+------------------------------------------------------------------------------+

2、对title字段创建全文索引

alter table article add fulltext index ft_index_title(title) with parser ngram;
Query OK, 0 rows affected (3 min 29.22 sec)
Records: 0  Duplicates: 0  Warnings: 0

3、会创建倒排索引(title字段越长长,创建的倒排索引越大)

112M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_1.ibd28M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_2.ibd20M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_3.ibd140M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_4.ibd128M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_5.ibd668M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_6.ibd

4、不建立全文索引搜索title的某个关键词

5、使用全文索引搜索某个关键词

响应时间有很大的提升

6、注意当搜索的关键词字符数大于2 (ngram_token_size定义大小)会出现不一致问题

普通搜索,实际中出现该关键词的记录数为6

全文搜索,出现关键字的记录数为9443

实际出现该关键字的记录数为1

全文搜索出现该关键词的记录数为3202

结论

当mysql 某字段中有固定的stopword 分词(英文的空格符,中文的“,”"-"等),对该字段建立全文索引,能快速搜索出现某个关键词的相关记录信息,实现简单搜索引擎的效果

当mysql 某字段没有固定的stopword 分词,使用内置解析器ngram 可将字段值分成固定数量(ngram_token_size定义大小)的关键词快速进行搜索;当搜索的关键词的字符数量不等于ngram_token_size定义大小时,会出现与实际情况不一致的问题

全文索引能快速搜索,也存在维护索引的开销;字段长度越大,创建的全文索引也越大,会影响DML语句的吞吐量,可用专门的全文搜索引擎ES来做这件事