从 MongoDB 及 Mysql 谈B/B+树

原文链接:https://blog.csdn.net/wwh578867817/article/details/50493940

前两天有位朋友邀请我回答个问题,为什么 MongoDB (索引)使用B-树而 Mysql 使用 B+树?我觉得这个问题非常好,从实际应用的角度来学习数据结构,没有比这更好的方法了。因为像 Mysql 和 MongoDB 这种经久考验的大型软件在设计上都是精益求精的,它们为什么选择这些数据结构?:)

本文从实际应用的角度来介绍以及分析B-树和B+树。

B-树由来
定义:B-树是一类树,包括B-树、B+树、B*树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。

定义只需要知道B-树允许每个节点有更多的子节点即可。子节点数量一般在上千,具体数量依赖外部存储器的特性。

先来看看为什么会出现B-树这类数据结构。

传统用来搜索的平衡二叉树有很多,如 AVL 树,红黑树等。这些树在一般情况下查询性能非常好,但当数据非常大的时候它们就无能为力了。原因当数据量非常大时,内存不够用,大部分数据只能存放在磁盘上,只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns,而磁盘在 10 ms 左右。速度相差了近 5 个数量级,磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能?减少磁盘 IO 次数,像 AVL 树,红黑树这类平衡二叉树从设计上无法“迎合”磁盘。
关于磁盘可参考 浅谈计算机中的存储模型(四)磁盘

上图是一颗简单的平衡二叉树,平衡二叉树是通过旋转来保持平衡的,而旋转是对整棵树的操作,若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log n(底数为2),这样逻辑上很近的节点实际可能非常远,无法很好的利用磁盘预读(局部性原理),所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

我们从“迎合”磁盘的角度来看看B-树的设计。

索引的效率依赖与磁盘 IO 的次数,快速索引需要有效的减少磁盘 IO 次数,如何快速索引呢?索引的原理其实是不断的缩小查找范围,就如我们平时用字典查单词一样,先找首字母缩小范围,再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快,B-树每次将范围分割为多个区间,区间越多,定位数据越快越精确。那么如果节点为区间范围,每个节点就较大了。所以新建节点时,直接申请页大小的空间(磁盘是按 block 分的,一般为 512 Byte。磁盘 IO 一次读取若干个 block,我们称为一页,具体大小和操作系统有关,一般为 4 k,8 k或 16 k),计算机内存分配是按页对齐的,这样就实现了一个节点只需要一次 IO。

上图是一棵简化的B-树,多叉的好处非常明显,有效的降低了B-树的高度,为底数很大的 log n,底数大小与节点的子节点数目有关,一般一棵B-树的高度在 3 层左右。层数低,每个节点区确定的范围更精确,范围缩小的速度越快。上面说了一个节点需要进行一次 IO,那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an),并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。

B-树
上图是一颗B-树,B-树的每个节点有 d~2d 个 key,2 这个因子指明了树的分裂及合并的规则,这个规则维持了B-树的平衡。

B-树的插入和删除就不具体介绍了,很多资料都描述了这一过程。在普通平衡二叉树中,插入删除后若不满足平衡条件则进行 旋转 操作,而在B-树中,插入删除后不满足条件则进行分裂及合并操作。

简单叙述下分裂及合并操作。

分裂:如果有一个节点有 2d 个 key,增加一个后为 2d+1 个 key,不符合上述规则 B-树的每个节点有 d~2d 个 key,大于 2d,则将该节点进行分裂,分裂为两个 d 个 key 的节点并将中值 key 归还给父节点。
合并:如果有一个节点有 d 个 key,删除一个后为 d-1 个 key,不符合上述规则 B-树的每个节点有 d~2d 个 key,小于 d,则将该节点进行合并,合并后若满足条件则合并完成,不满足则均分为两个节点。

B-树的查找

我们来看看B-树的查找,假设每个节点有 n 个 key值,被分割为 n+1 个区间,注意,每个 key 值紧跟着 data 域,这说明B-树的 key 和 data 是聚合在一起的。一般而言,根节点都在内存中,B-树以每个节点为一次磁盘 IO,比如上图中,若搜索 key 为 25 节点的 data,首先在根节点进行二分查找(因为 keys 有序,二分最快),判断 key 25 小于 key 50,所以定位到最左侧的节点,此时进行一次磁盘 IO,将该节点从磁盘读入内存,接着继续进行上述过程,直到找到该 key 为止。

查找伪代码

Data* BTreeSearch(Root *node, Key key)
{
Data* data;

if(root == NULL)
return NULL;
data = BinarySearch(node);
if(data->key == key)
{
return data;
}else{
node = ReadDisk(data->next);
BTreeSearch(node, key);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
B+树
B+树是B-树的变种,它与B-树的不同之处在于:

在B+树中,key 的副本存储在内部节点,真正的 key 和 data 存储在叶子节点上 。
n 个 key 值的节点指针域为 n 而不是 n+1。
如下图为一颗B+树:

因为内节点并不存储 data,所以一般B+树的叶节点和内节点大小不同,而B-树的每个节点大小一般是相同的,为一页。

为了增加 区间访问性,一般会对B+树做一些优化。
如下图带顺序访问的B+树。

B-树和B+树的区别
1.B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。

如下所示B-树/B+树查询节点 key 为 50 的 data。

B-树

从上图可以看出,key 为 50 的节点就在第一层,B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。

B+树

由于B+树所有的 data 域都在根节点,所以查询 key 为 50的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)。

2.B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。

根据空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

B+树可以很好的利用局部性原理,若我们访问节点 key为 50,则 key 为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数。
当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

3.B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确

这个很好理解,由于B-树节点内部每个 key 都带着 data 域,而B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的,一次磁盘 IO 会读取若干个 block,具体和操作系统有关,那么由于磁盘 IO 数据大小是固定的,在一次 IO 中,单个元素越小,量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树,从这点来看B+树相对B-树磁盘 IO 次数少。

从上图可以看出相同大小的区域,B-树仅有 2 个 key,而B+树有 3 个 key。

为什么 MongoDB 索引选择B-树,而 Mysql 索引选择B+树
这些内容了解后,我们来看为什么 MongoDB 索引选择B-树,而 Mysql (InooDB 引擎)索引选择B+树。

Mysql 大家应该比较熟悉,传统的关系型数据库,下面介绍下 MongoDB。

来看下 wiki 百科上 MongoDB 的定义:

MongoDB (from humongous) is a cross-platform document-oriented database. Classified as a NoSQL database, MongoDB eschews the traditional table-based relational database structure in favor of JSON-like documents with dynamic schemas (MongoDB calls the format BSON)

这段话的大致意思是 MongoDB 是文档型的数据库,是一种 nosql,它使用类 Json 格式保存数据。

文档型数据库和我们常见的关系型数据库不同,一般使用 XML 或 Json 格式来保存数据,归属于聚合型数据库。

键值数据库也属于聚合型数据库,熟悉 Redis 的同学应该很好理解。

举个例子:

加入我们要建立一个电子商务网站,类似淘宝这种将商品销售给用户,那么必须存储用户信息、商品目录、订单、收货地址、账单地址、付款方式等。

看下传统的关系型数据库是如何存储的:

聚合型数据库存储模型:

用类似 Json 的格式表示如下:

//Customer
{
“id”:1,
“name”:Tom,
“billingAddress”:[{“city”:”China”}]
}

//Orders
{
“id”:99,
“orderItem”:[
“productId”27,
“price”:100,
“productName”:book
],
“shippingAddress”:[{“city”:”china”}],
“orderPayment”:[

]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
相对于 Mysql 关系型数据库,MongoDB 这类 nosql 适用于数据模型简单,性能要求高的场合

为什么 MongoDB 使用B-树
MongoDB 是一种 nosql,也存储在磁盘上,被设计用在 数据模型简单,性能要求高的场合。性能要求高,看看B/B+树的区别第一点:

B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)

我们说过,尽可能少的磁盘 IO 是提高性能的有效手段。MongoDB 是聚合型数据库,而 B-树恰好 key 和 data 域聚合在一起。

为什么 Mysql 使用B+树
Mysql 是一种关系型数据库,区间访问是常见的一种情况,而 B-树并不支持区间访问(可参见上图),而B+树由于数据全部存储在叶子节点,并且通过指针串在一起,这样就很容易的进行区间遍历甚至全部遍历。见B/B+树的区别第二点:

B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。

其次B+树的查询效率更加稳定,数据全部存储在叶子节点,查询时间复杂度固定为 O(log n)。

最后第三点:

B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确
————————————————
版权声明:本文为CSDN博主「夏天的技术博客」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/wwh578867817/article/details/50493940

VARCHAR(M)最多能存储的数据

我们知道对于VARCHAR(M)类型的列最多可以占用65535个字节。其中的M代表该类型最多存储的字符数量,如果我们使用ascii字符集的话,一个字符就代表一个字节,我们看看VARCHAR(65535)是否可用: mysql> CREATE TABLE varchar_size_demo(

-> c VARCHAR(65535)

-> ) CHARSET=ascii ROW_FORMAT=Compact;
ERROR 1118 (42000): Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes storage overhead, check the manual. You have to change som mysql>

从报错信息里可以看出,MySQL对一条记录占用的最大存储空间是有限制的,除了BLOB或者TEXT类型的列之外,其他所有的列(不包括隐藏列和记录头信息)占用的字节长度加起来不能超过65535个字 节。所以MySQL服务器建议我们把存储类型改为TEXT或者BLOB的类型。这个65535个字节除了列本身的数据之外,还包括一些其他的数据(storage overhead),比如说我们为了存储一个VARCHAR(M)类型 的列,其实需要占用3部分存储空间:

真实数据
真实数据占用字节的长度
NULL值标识,如果该列有NOT NULL属性则可以没有这部分存储空间

如果该VARCHAR类型的列没有NOT NULL属性,那最多只能存储65532个字节的数据,因为真实数据的长度可能占用2个字节,NULL值标识需要占用1个字节:

CREATE TABLE varchar_size_demo( c VARCHAR(65532)

) CHARSET=ascii ROW_FORMAT=Compact; Query OK, 0 rows affected (0.02 sec)

如果VARCHAR类型的列有NOT NULL属性,那最多只能存储65533个字节的数据,因为真实数据的长度可能占用2个字节,不需要NULL值标识:

mysql> DROP TABLE varchar_size_demo; Query OK, 0 rows affected (0.01 sec)

CREATE TABLE varchar_size_demo( c VARCHAR(65533) NOT NULL

) CHARSET=ascii ROW_FORMAT=Compact; Query OK, 0 rows affected (0.02 sec)

如果VARCHAR(M)类型的列使用的不是ascii字符集,那会怎么样呢?来看一下:

mysql> DROP TABLE varchar_size_demo; Query OK, 0 rows affected (0.00 sec)

CREATE TABLE varchar_size_demo( c VARCHAR(65532)

) CHARSET=gbk ROW_FORMAT=Compact;
ERROR 1074 (42000): Column length too big for column ‘c’ (max = 32767); use BLOB or TEXT instead

CREATE TABLE varchar_size_demo( c VARCHAR(65532)

) CHARSET=utf8 ROW_FORMAT=Compact;
ERROR 1074 (42000): Column length too big for column ‘c’ (max = 21845); use BLOB or TEXT instead

从执行结果中可以看出,如果VARCHAR(M)类型的列使用的不是ascii字符集,那M的最大取值取决于该字符集表示一个字符最多需要的字节数。在列的值允许为NULL的情况下,gbk字符集表示一个字符最多 需要2个字节,那在该字符集下,M的最大取值就是32766(也就是:65532/2),也就是说最多能存储32766个字符;utf8字符集表示一个字符最多需要3个字节,那在该字符集下,M的最大取值就 是21844,就是说最多能存储21844(也就是:65532/3)个字符。

小贴士: 上述所言在列的值允许为NULL的情况下,gbk字符集下M的最大取值就是32766,utf8字符集下M的最大取值就是21844,这都是在表中只有一个字段的情况下说的,一定要记住一个行 中的所有列(不包括隐藏列和记录头信息)占用的字节长度加起来不能超过65535个字节!

Elasticsearch 如何做到快速检索 – 倒排索引的秘密

“All problems in computer science can be solved by another level of indirection.”

– David J. Wheeler

“计算机世界就是 trade-off 的艺术”

摘抄了一篇比较好的,上面图和方法在很多博客都被引用,但是相对组织的较好。

一、前言

最近接触的几个项目都使用到了 Elasticsearch (以下简称 ES ) 来存储数据和对数据进行搜索分析,就对 ES 进行了一些学习。本文整理自我自己的一次技术分享。

本文不会关注 ES 里面的分布式技术、相关 API 的使用,而是专注分享下 ”ES 如何快速检索“ 这个主题上面。这个也是我在学习之前对 ES 最感兴趣的部分。


本文大致包括以下内容:

  • 关于搜索

    • 传统关系型数据库和 ES 的差别

    • 搜索引擎原理

  • 细究倒排索引

    • 倒排索引具体是个什么样子的(posting list -> term dic -> term index)

    • 关于 postings list 的一些巧技 (FOR、Roaring Bitmaps)

    • 如何快速做联合查询?

二、关于搜索

先设想一个关于搜索的场景,假设我们要搜索一首诗句内容中带“前”字的古诗,

用 传统关系型数据库和 ES 实现会有什么差别?

如果用像 MySQL 这样的 RDBMS 来存储古诗的话,我们应该会去使用这样的 SQL 去查询

select name from poems where content like "%前%";
复制代码

这种我们称为顺序扫描法,需要遍历所有的记录进行匹配。

不但效率低,而且不符合我们搜索时的期望,比如我们在搜索“ABCD”这样的关键词时,通常还希望看到”A”,”AB”,”CD”,“ABC”的搜索结果。

于是乎就有了专业的搜索引擎,比如我们今天的主角 — ES。

搜索引擎原理

搜索引擎的搜索原理简单概括的话可以分为这么几步,

  • 内容爬取,停顿词过滤

    比如一些无用的像”的”,“了”之类的语气词/连接词

  • 内容分词,提取关键词

  • 根据关键词建立倒排索引

  • 用户输入关键词进行搜索

这里我们就引出了一个概念,也是我们今天的要剖析的重点 – 倒排索引。也是 ES 的核心知识点。

如果你了解 ES 应该知道,ES 可以说是对 Lucene 的一个封装,里面关于倒排索引的实现就是通过 lucene 这个 jar 包提供的 API 实现的,所以下面讲的关于倒排索引的内容实际上都是 lucene 里面的内容。

三、倒排索引

首先我们还不能忘了我们之前提的搜索需求,先看下建立倒排索引之后,我们上述的查询需求会变成什么样子,

这样我们一输入“前”,借助倒排索引就可以直接定位到符合查询条件的古诗。

当然这只是一个很大白话的形式来描述倒排索引的简要工作原理。在 ES 中,这个倒排索引是具体是个什么样的,怎么存储的等等,这些才是倒排索引的精华内容。

1. 几个概念

在进入下文之前,先描述几个前置概念。

term

关键词这个东西是我自己的讲法,在 ES 中,关键词被称为 term

postings list

还是用上面的例子,{静夜思, 望庐山瀑布}是 “前” 这个 term 所对应列表。在 ES 中,这些被描述为所有包含特定 term 文档的 id 的集合。由于整型数字 integer 可以被高效压缩的特质,integer 是最适合放在 postings list 作为文档的唯一标识的,ES 会对这些存入的文档进行处理,转化成一个唯一的整型 id。

再说下这个 id 的范围,在存储数据的时候,在每一个 shard 里面,ES 会将数据存入不同的 segment,这是一个比 shard 更小的分片单位,这些 segment 会定期合并。在每一个 segment 里面都会保存最多 2^31 个文档,每个文档被分配一个唯一的 id,从0(2^31)-1

相关的名词都是 ES 官方文档给的描述,后面参考材料中都可以找到出处。

2. 索引内部结构

上面所描述的倒排索引,仅仅是一个很粗糙的模型。真的要在实际生产中使用,当然还差的很远。

在实际生产场景中,比如 ES 最常用的日志分析,日志内容进行分词之后,可以得到多少的 term?

那么如何快速的在海量 term 中查询到对应的 term 呢?遍历一遍显然是不现实的。

term dictionary

于是乎就有了 term dictionary,ES 为了能快速查找到 term,将所有的 term 排了一个序,二分法查找。是不是感觉有点眼熟,这不就是 MySQL 的索引方式的,直接用 B+树建立索引词典指向被索引的数据。

term index

但是问题又来了,你觉得 Term Dictionary 应该放在哪里?肯定是放在内存里面吧?磁盘 io 那么慢。就像 MySQL 索引就是存在内存里面了。

但是如果把整个 term dictionary 放在内存里面会有什么后果呢?

内存爆了…

别忘了,ES 默认可是会对全部 text 字段进行索引,必然会消耗巨大的内存,为此 ES 针对索引进行了深度的优化。在保证执行效率的同时,尽量缩减内存空间的占用。

于是乎就有了 term index

Term index 从数据结构上分类算是一个“Trie 树”,也就是我们常说的字典树。这是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。

这棵树不会包含所有的 term,它包含的是 term 的一些前缀(这也是字典树的使用场景,公共前缀)。通过 term index 可以快速地定位到 term dictionary 的某个 offset,然后从这个位置再往后顺序查找。就想右边这个图所表示的。(怎么样,像不像我们查英文字典,我们定位 S 开头的第一个单词,或者定位到 Sh 开头的第一个单词,然后再往后顺序查询)

lucene 在这里还做了两点优化,一是 term dictionary 在磁盘上面是分 block 保存的,一个 block 内部利用公共前缀压缩,比如都是 Ab 开头的单词就可以把 Ab 省去。二是 term index 在内存中是以 FST(finite state transducers)的数据结构保存的。

FST 有两个优点:

  • 空间占用小。通过对词典中单词前缀和后缀的重复利用,压缩了存储空间
  • 查询速度快。O(len(str)) 的查询时间复杂度。

FST 的理论比较复杂,本文不细讲

延伸阅读:https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

OK,现在我们能得到 lucene 倒排索引大致是个什么样子的了。

四、关于 postings list 的一些巧技

在实际使用中,postings list 还需要解决几个痛点,

  • postings list 如果不进行压缩,会非常占用磁盘空间,
  • 联合查询下,如何快速求交并集(intersections and unions)

对于如何压缩,可能会有人觉得没有必要,”posting list 不是已经只存储文档 id 了吗?还需要压缩?”,但是如果在 posting list 有百万个 doc id 的情况,压缩就显得很有必要了。(比如按照朝代查询古诗?),至于为啥需要求交并集,ES 是专门用来搜索的,肯定会有很多联合查询的需求吧 (AND、OR)。

按照上面的思路,我们先将如何压缩。

1. 压缩

Frame of Reference

在 lucene 中,要求 postings lists 都要是有序的整形数组。这样就带来了一个很好的好处,可以通过 增量编码(delta-encode)这种方式进行压缩。

比如现在有 id 列表 [73, 300, 302, 332, 343, 372],转化成每一个 id 相对于前一个 id 的增量值(第一个 id 的前一个 id 默认是 0,增量就是它自己)列表是[73, 227, 2, 30, 11, 29]在这个新的列表里面,所有的 id 都是小于 255 的,所以每个 id 只需要一个字节存储

实际上 ES 会做的更加精细,

它会把所有的文档分成很多个 block,每个 block 正好包含 256 个文档,然后单独对每个文档进行增量编码,计算出存储这个 block 里面所有文档最多需要多少位来保存每个 id,并且把这个位数作为头信息(header)放在每个 block 的前面。这个技术叫 Frame of Reference

上图也是来自于 ES 官方博客中的一个示例(假设每个 block 只有 3 个文件而不是 256)。

FOR 的步骤可以总结为:

进过最后的位压缩之后,整型数组的类型从固定大小 (8,16,32,64 位)4 种类型,扩展到了[1-64] 位共 64 种类型。

通过以上的方式可以极大的节省 posting list 的空间消耗,提高查询性能。不过 ES 为了提高 filter 过滤器查询的性能,还做了更多的工作,那就是缓存

Roaring Bitmaps (for filter cache)

在 ES 中,可以使用 filters 来优化查询,filter 查询只处理文档是否匹配与否,不涉及文档评分操作,查询的结果可以被缓存。

对于 filter 查询,es 提供了 filter cache 这种特殊的缓存,filter cache 用来存储 filters 得到的结果集。缓存 filters 不需要太多的内存,它只保留一种信息,即哪些文档与 filter 相匹配。同时它可以由其它的查询复用,极大地提升了查询的性能。

我们上面提到的 Frame Of Reference 压缩算法对于 postings list 来说效果很好,但对于需要存储在内存中的 filter cache 等不太合适。

filter cache 会存储那些经常使用的数据,针对 filter 的缓存就是为了加速处理效率,对压缩算法要求更高。

对于这类 postings list,ES 采用不一样的压缩方式。那么让我们一步步来。

首先我们知道 postings list 是 Integer 数组,具有压缩空间。

假设有这么一个数组,我们第一个压缩的思路是什么?用位的方式来表示,每个文档对应其中的一位,也就是我们常说的位图,bitmap。

它经常被作为索引用在数据库、查询引擎和搜索引擎中,并且位操作(如 and 求交集、or 求并集)之间可以并行,效率更好。

但是,位图有个很明显的缺点,不管业务中实际的元素基数有多少,它占用的内存空间都恒定不变。也就是说不适用于稀疏存储。业内对于稀疏位图也有很多成熟的压缩方案,lucene 采用的就是roaring bitmaps

我这里用简单的方式描述一下这个压缩过程是怎么样,

将 doc id 拆成高 16 位,低 16 位。对高位进行聚合 (以高位做 key,value 为有相同高位的所有低位数组),根据低位的数据量 (不同高位聚合出的低位数组长度不相同),使用不同的 container(数据结构) 存储。

  • len<4096 ArrayContainer 直接存值

  • len>=4096 BitmapContainer 使用 bitmap 存储

分界线的来源:value 的最大总数是为2^16=65536. 假设以 bitmap 方式存储需要 65536bit=8kb,而直接存值的方式,一个值 2 byte,4K 个总共需要2byte*4K=8kb。所以当 value 总量 <4k 时,使用直接存值的方式更节省空间。

空间压缩主要体现在:

  • 高位聚合 (假设数据中有 100w 个高位相同的值,原先需要 100w2byte,现在只要 12byte)

  • 低位压缩

缺点就在于位操作的速度相对于原生的 bitmap 会有影响。

这就是 trade-off 呀。平衡的艺术。

2. 联合查询

讲完了压缩,我们再来讲讲联合查询。

先讲简单的,如果查询有 filter cache,那就是直接拿 filter cache 来做计算,也就是说位图来做 AND 或者 OR 的计算。

如果查询的 filter 没有缓存,那么就用 skip list 的方式去遍历磁盘上的 postings list。

以上是三个 posting list。我们现在需要把它们用 AND 的关系合并,得出 posting list 的交集。首先选择最短的 posting list,逐个在另外两个 posting list 中查找看是否存在,最后得到交集的结果。遍历的过程可以跳过一些元素,比如我们遍历到绿色的 13 的时候,就可以跳过蓝色的 3 了,因为 3 比 13 要小。

用 skip list 还会带来一个好处,还记得前面说的吗,postings list 在磁盘里面是采用 FOR 的编码方式存储的

会把所有的文档分成很多个 block,每个 block 正好包含 256 个文档,然后单独对每个文档进行增量编码,计算出存储这个 block 里面所有文档最多需要多少位来保存每个 id,并且把这个位数作为头信息(header)放在每个 block 的前面。

因为这个 FOR 的编码是有解压缩成本的。利用 skip list,除了跳过了遍历的成本,也跳过了解压缩这些压缩过的 block 的过程,从而节省了 cpu

五、总结

下面我们来做一个技术总结(感觉有点王刚老师的味道😂)

  • 为了能够快速定位到目标文档,ES 使用倒排索引技术来优化搜索速度,虽然空间消耗比较大,但是搜索性能提高十分显著。
  • 为了能够在数量巨大的 terms 中快速定位到某一个 term,同时节约对内存的使用和减少磁盘 io 的读取,lucene 使用 “term index -> term dictionary -> postings list” 的倒排索引结构,通过 FST 压缩放入内存,进一步提高搜索效率。
  • 为了减少 postings list 的磁盘消耗,lucene 使用了 FOR(Frame of Reference)技术压缩,带来的压缩效果十分明显。
  • ES 的 filter 语句采用了 Roaring Bitmap 技术来缓存搜索结果,保证高频 filter 查询速度的同时降低存储空间消耗。
  • 在联合查询时,在有 filter cache 的情况下,会直接利用位图的原生特性快速求交并集得到联合查询结果,否则使用 skip list 对多个 postings list 求交并集,跳过遍历成本并且节省部分数据的解压缩 cpu 成本

Elasticsearch 的索引思路

将磁盘里的东西尽量搬进内存,减少磁盘随机读取次数 (同时也利用磁盘顺序读特性),结合各种压缩算法,用及其苛刻的态度使用内存。

所以,对于使用 Elasticsearch 进行索引时需要注意:

  • 不需要索引的字段,一定要明确定义出来,因为默认是自动建索引的
  • 同样的道理,对于 String 类型的字段,不需要 analysis 的也需要明确定义出来,因为默认也是会 analysis 的
  • 选择有规律的 ID 很重要,随机性太大的 ID(比如 Java 的 UUID) 不利于查询

最后说一下,技术选型永远伴随着业务场景的考量,每种数据库都有自己要解决的问题(或者说擅长的领域),对应的就有自己的数据结构,而不同的使用场景和数据结构,需要用不同的索引,才能起到最大化加快查询的目的。

这篇文章讲的虽是 Lucene 如何实现倒排索引,如何精打细算每一块内存、磁盘空间、如何用诡谲的位运算加快处理速度,但往高处思考,再类比一下 MySQL,你就会发现,虽然都是索引,但是实现起来,截然不同。笼统的来说,b-tree 索引是为写入优化的索引结构。当我们不需要支持快速的更新的时候,可以用预先排序等方式换取更小的存储空间,更快的检索速度等好处,其代价就是更新慢,就像 ES。

希望本篇文章能给你带来一些收获~

参考文档

  • https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps
  • https://www.elastic.co/cn/blog/found-elasticsearch-from-the-bottom-up
  • http://blog.mikemccandless.com/2014/05/choosing-fast-unique-identifier-uuid.html
  • https://www.infoq.cn/article/database-timestamp-02
  • https://zhuanlan.zhihu.com/p/137574234

作者:Richard_Yi
链接:https://juejin.im/post/6889020742366920712
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Mycat【数据库方式】实现全局序列号

说明:本文参考mycat官方提供的文档,结合自己的实践以及理解,做出如下整理,并附带一个分库分表的插入数据例子。
原理
在数据库中建立一张表,存放sequence名称(name),sequence当前值(current_value),步长(increment int类型每次读取多少个sequence,假设为K)等信息;
Sequence获取步骤:
1)当初次使用该sequence时,根据传入的sequence名称,从数据库这张表中读取current_value,和increment到MyCat中,并将数据库中的current_value设置为原current_value值+increment值;
2)MyCat将读取到current_value+increment作为本次要使用的sequence值,下次使用时,自动加1,当使用increment次后,执行步骤1)相同的操作.
3)MyCat负责维护这张表,用到哪些sequence,只需要在这张表中插入一条记录即可。若某次读取的sequence没有用完,系统就停掉了,则这次读取的sequence剩余值不会再使用。
配置方式
server.xml配置:

<system><property name=”sequnceHandlerType”>1</property></system>
1
注:sequnceHandlerType 需要配置为1,表示使用数据库方式生成sequence.
数据库配置:
1)创建sequence表

CREATE TABLE MYCAT_SEQUENCE (
name VARCHAR (50) NOT NULL comment “名称”,
current_value INT NOT NULL comment “当前值”,
increment INT NOT NULL DEFAULT 100 comment “步长”,
PRIMARY KEY (name)
) ENGINE = INNODB;
1
2
3
4
5
6
2)创建相关function

#取当前squence的值
DROP FUNCTION IF EXISTS mycat_seq_currval;
DELIMITER $$
CREATE FUNCTION mycat_seq_currval(seq_name VARCHAR(50))RETURNS VARCHAR(64) CHARSET ‘utf8′
BEGIN
DECLARE retval VARCHAR(64);
SET retval=’-999999999,NULL’;
SELECT CONCAT(CAST(current_value AS CHAR),’,’,CAST(increment AS CHAR)) INTO retval FROM
MYCAT_SEQUENCE WHERE NAME = seq_name;
RETURN retval;
END$$
DELIMITER ;

#设置 sequence 值
DROP FUNCTION IF EXISTS mycat_seq_setval;
DELIMITER $$
CREATE FUNCTION mycat_seq_setval(seq_name VARCHAR(50),VALUE INTEGER) RETURNS VARCHAR(64) CHARSET ‘utf8’
BEGIN
UPDATE MYCAT_SEQUENCE SET current_value = VALUE WHERE NAME = seq_name;
RETURN mycat_seq_currval(seq_name);
END$$
DELIMITER ;

#取下一个sequence的值
DROP FUNCTION IF EXISTS mycat_seq_nextval;
DELIMITER $$
CREATE FUNCTION mycat_seq_nextval(seq_name VARCHAR(50)) RETURNS VARCHAR(64) CHARSET ‘utf8′
BEGIN
UPDATE MYCAT_SEQUENCE SET current_value = current_value + increment
WHERE NAME = seq_name;
RETURN mycat_seq_currval(seq_name);
END$$
DELIMITER ;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
3)sequence_db_conf.properties相关配置,指定sequence相关配置在哪个节点上:
例如:

COMPANY=dn3
1
注:COMPANY为表名,必须大写,dn3为schema.xml配置的dataNode节点。建议专门独立一个数据库,存放sequence表和相关的function,方便维护管理和隔离。

注意:MYCAT_SEQUENCE表和以上的3个function,需要放在同一个节点上。function请直接在具体节点的数据库上执行,如果执行的时候报:
you might want to use the less safe log_bin_trust_function_creators variable
需要对数据库做如下设置:
windows下my.ini[mysqld]加上log_bin_trust_function_creators=1
linux下/etc/my.cnf下my.ini[mysqld]加上log_bin_trust_function_creators=1
修改完后,即可在mysql数据库中执行上面的函数.
使用示例:

SELECT next value for MYCATSEQ_SAM_TEST
insert into sam_test(id_,name_) values(next value for MYCATSEQ_SAM_TEST,’test’);
# 数据库表定义了自增,在mycat也定义了主键和自增,可以用如下方式
insert into sam_test(name_) values(‘test’);
1
2
3
4
测试
1.配置schema.xml

<schema name=”TESTDB” checkSQLschema=”false” sqlMaxLimit=”100″>
<table name=”company” dataNode=”dn1,dn2″ rule=”companyRule” primaryKey=”id” autoIncrement=”true” />
</schema>

<dataNode name=”dn1″ dataHost=”localhost1″ database=”mycat_test” />
<dataNode name=”dn2″ dataHost=”localhost1″ database=”mycat_test2″ />
<dataNode name=”dn3″ dataHost=”localhost2″ database=”testmycat” />

<dataHost name=”localhost1″ maxCon=”1000″ minCon=”10″ balance=”0″
writeType=”0″ dbType=”mysql” dbDriver=”native” switchType=”1″ slaveThreshold=”100″>
<heartbeat>select user()</heartbeat>
<writeHost host=”hostM1″ url=”192.168.1.95:3306″ user=”admin” password=”admin”/>
<writeHost host=”hostM2″ url=”192.138.1.112:3306″ user=”root” password=”root”/>
</dataHost>
<!– 存放sequence数据库 –>
<dataHost name=”localhost2″ maxCon=”1000″ minCon=”10″ balance=”0″
writeType=”0″ dbType=”mysql” dbDriver=”native” switchType=”1″ slaveThreshold=”100″>
<heartbeat>select user()</heartbeat>
<writeHost host=”localhost2M2″ url=”192.138.1.112:3306″ user=”root” password=”root”/>
</dataHost>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2.配置server.xml

<property name=”sequnceHandlerType”>1</property><!– 1:使用数据库方式生成sequence –>
1
3.配置rule.xml

<tableRule name=”companyRule”>
<rule>
<columns>id</columns>
<algorithm>mod-long</algorithm>
</rule>
</tableRule>
<function name=”mod-long” class=”org.opencloudb.route.function.PartitionByMod”>
<!– how many data nodes –>
<property name=”count”>2</property>
</function>
1
2
3
4
5
6
7
8
9
10
4.配置sequence_db_conf.properties

COMPANY=dn3
1
5.数据库配置文件修改my.ini

log_bin_trust_function_creators=1
# 忽略大小写
lower_case_table_names=1
1
2
3
6.数据库表
1)分别到192.168.1.95的mycat_test数据库和mycat_test2数据库新建如下的表,由于是分库分表,所以两边都要创建。

DROP TABLE IF EXISTS `company`;
CREATE TABLE `company` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(255) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
1
2
3
4
5
6
注:只有数据库和mycat都设置AUTO_INCREMENT才能通过mycat命令LAST_INSERT_ID()获取插入的id
2)到192.168.1.112的testmycat数据库中执行上面的创建sequence和function过程。
3)插入数据到MYCAT_SEQUENCE表

insert into MYCAT_SEQUENCE(name,current_value,increment) values(‘COMPANY’,19,5);
1
7.mycat测试
配置完之后,重启mycat
执行

insert into company(id,name) values (next value for MYCATSEQ_COMPANY,”test”)

insert into company(name) values (“test”)
1
2
3
插入数据成功后
执行

select LAST_INSERT_ID()
1
可以看到本次插入的id

小结
如果要获取插入数据后的id,必须同时在mysql和mycat设置表的自增。
sequence_db_conf.properties配置的表名必须大写。
存放sequence表和function在同一个数据库中,且只有一个。
以上【Sequence获取步骤】是mycat原理,注意理解。
———————
作者:黄晓杰Aries
来源:CSDN
原文:https://blog.csdn.net/u010956470/article/details/70837876
版权声明:本文为博主原创文章,转载请附上博文链接!

mycat配置及使用

Mycat数据库分库分表中间件

详细文档在http://www.mycat.io/

本次主要想做分库分表的操作,将mysql分别部署在不同的机器上,mycat作为Proxy。

安装非常简单,下载相应的包就行。但是需要安装最新版本的java


yum install java-1.8.0-openjdk-src.x86_64

之后需要进行三个配置文件的配置

1,server.xml


<property name="sequnceHandlerType">3</property>

 

2,schema.xml

<dataNode name=”dn1″ dataHost=”localhost1″ database=”tt” />
<dataNode name=”dn2″ dataHost=”localhost2″ database=”tt” />

<dataHost name=”localhost2″ maxCon=”1000″ minCon=”10″ balance=”0″
writeType=”0″ dbType=”mysql” dbDriver=”native” switchType=”1″ slaveThreshold=”100″>
<heartbeat>select user()</heartbeat>
<writeHost host=”hostS1″ url=”IP:PORT” user=”root”
password=”XXX” />
</dataHost>

<dataHost name=”localhost2″ maxCon=”1000″ minCon=”10″ balance=”0″
writeType=”0″ dbType=”mysql” dbDriver=”native” switchType=”1″ slaveThreshold=”100″>
<heartbeat>select user()</heartbeat>
<writeHost host=”hostS1″ url=”IP:PORT” user=”root”
password=”XXX” />
</dataHost>

3,rule.xml

<function name=”mod-long” class=”io.mycat.route.function.PartitionByMod”>
<!– how many data nodes –>
<property name=”count”>2</property>
</function>

然后就可以根据主键id平均请求到不同的mysql。作为水平扩展。这里自增主键的方式可以参考官方文档。我用0的时候总是偶数,分表非常不友好。

wordpress挂站–Error establishing a database connection

今天莫名其妙我的博客出现Error establishing a database connection,一看应该是数据连接不上了。首先看了下wp-config.php,发现无异常。重启nginx,更换php5均没有效果。网上查了下,说是http://blog.csdn.net/mwb310/article/details/53009920,众说纷纭,有文件格式错误,mysql版本错误等等,试了均无效。

想着不如先把sql dump一份备份,所以

mysqldump -uxxx -pxxx --dataname >wordpress.log

发现:

 

warning : 250 clients are using or haven’t closed the table properly
status : OK
wangchunwei.wp_statistics_search
warning : 156 clients are using or haven’t closed the table properly
status : OK
wangchunwei.wp_statistics_useronline
warning : 252 clients are using or haven’t closed the table properly
status : OK
wangchunwei.wp_statistics_visit
warning : 252 clients are using or haven’t closed the table properly
status : OK
wangchunwei.wp_statistics_visitor
warning : 252 clients are using or haven’t closed the table properly
status : OK
wangchunwei.wp_term_relationships
warning : 32 clients are using or haven’t closed the table properly
status : OK
wangchunwei.wp_term_taxonomy
warning : 31 clients are using or haven’t closed the table properly
status : OK

 

 

mysqldump: Got error: 145: Table ‘./xxx/wp_options’ is marked as crashed and should be repaired when using LOCK TABLES

网上参考了:

修复 MySQL 数据库数据表问题可以由 mysqlcheck 来解决,先用 mysqlcheck 查看一下:

# mysqlcheck -u root -p wordpress
Enter password:

然后添加 –auto-repair 参数自动修复,最好修复前备份一下数据库:

# mysqldump -u root -p wordpress > wordpress.sql
Enter password:

# mysqlcheck -u root -p wordpress --auto-repair
Enter password:
wordpress.wp_commentmeta
error    : Table upgrade required. Please do "REPAIR TABLE `wp_commentmeta`" or dump/reload to fix it!
wordpress.wp_comments
error    : Table upgrade required. Please do "REPAIR TABLE `wp_comments`" or dump/reload to fix it!
wordpress.wp_links
error    : Table upgrade required. Please do "REPAIR TABLE `wp_links`" or dump/reload to fix it!
wordpress.wp_options
error    : Table upgrade required. Please do "REPAIR TABLE `wp_options`" or dump/reload to fix it!
wordpress.wp_postmeta
error    : Table upgrade required. Please do "REPAIR TABLE `wp_postmeta`" or dump/reload to fix it!
wordpress.wp_posts
error    : Table upgrade required. Please do "REPAIR TABLE `wp_posts`" or dump/reload to fix it!
wordpress.wp_term_relationships                OK
wordpress.wp_term_taxonomy
error    : Table upgrade required. Please do "REPAIR TABLE `wp_term_taxonomy`" or dump/reload to fix it!
wordpress.wp_terms
error    : Table upgrade required. Please do "REPAIR TABLE `wp_terms`" or dump/reload to fix it!
wordpress.wp_usermeta
error    : Table upgrade required. Please do "REPAIR TABLE `wp_usermeta`" or dump/reload to fix it!
wordpress.wp_users
error    : Table upgrade required. Please do "REPAIR TABLE `wp_users`" or dump/reload to fix it!

Repairing tables
wordpress.wp_commentmeta                       OK
wordpress.wp_comments                          OK
wordpress.wp_links                             OK
wordpress.wp_options                           OK
wordpress.wp_postmeta                          OK
wordpress.wp_posts                             OK
wordpress.wp_term_taxonomy                     OK
wordpress.wp_terms                             OK
wordpress.wp_usermeta                          OK
wordpress.wp_users                             OK

网站恢复了!应该是链接没有释放

Mysql replace 与 insert on duplicate效率分析

导读

我们在向数据库里批量插入数据的时候,会遇到要将原有主键或者unique索引所在记录更新的情况,而如果没有主键或者unique索引冲突的时候,直接执行插入操作。

这种情况下,有三种方式执行:

直接

直接每条select, 判断, 然后insert,毫无疑问,这是最笨的方法了,不断的查询判断,有主键或索引冲突,执行update,否则执行insert. 数据量稍微大一点这种方式就不行了。

稍微高级一些的方式。

replace

这是mysql自身的一个语法,使用 replace 的时候。其语法为:

replace into tablename (f1, f2, f3) values(vf1, vf2, vf3),(vvf1, vvf2, vvf3)

这中语法会自动查询主键或索引冲突,如有冲突,他会先删除原有的数据记录,然后执行插入新的数据。

insert on duplicate key.

这也是一种方式,mysql的insert操作中也给了一种方式,语法如下:

INSERT INTO table (a,b,c) VALUES (1,2,3)
  ON DUPLICATE KEY UPDATE c=c+1;

在insert时判断是否已有主键或索引重复,如果有,一句update后面的表达式执行更新,否则,执行插入。

第一种方式不说了,replace和insert on duplicate key这两种方式,哪中效率更高一些呢,毕竟,我们的执行sql,追求的就是高效。

分析

在最终实践结果中,得到接过如下:
在数据库数据量很少的时候, 这两种方式都很快,无论是直接的插入还是有冲突时的更新,都不错,但在数据库表的内容数量比较大(如百万级)的时候,两种方式就不太一样了,

首先是直接的插入操作,两种的插入效率都略低, 比如直接向表里插入1000条数据(百万级的表(innodb引擎)),二者都差不多需要5,6甚至十几秒。究其原因,我的主机性能是一方面,但在向大数据表批量插入数据的时候,每次的插入都要维护索引的, 索引固然可以提高查询的效率,但在更新表尤其是大表的时候,索引就成了一个不得不考虑的问题了。

其次是更新表,这里的更新的时候是带主键值的(因为我是从另一个表获取数据再插入,要求主键不能变) 同样直接更新1000条数据, replace的操作要比insert on duplicate的操作低太多太多, 当insert瞬间完成(感觉)的时候,replace要7,8s, replace慢的原因我是知道的,在更新数据的时候,要先删除旧的,然后插入新的,在这个过程中,还要重新维护索引,所以速度慢,但为何insert on duplicate的更新却那么快呢。 在向老大请教后,终于知道,insert on duplicate 的更新操作虽然也会更新数据,但其对主键的索引却不会有改变,也就是说,insert on duplicate 更新对主键索引没有影响.因此对索引的维护成本就低了一些(如果更新的字段不包括主键,那就要另说了)。

题外话:

在向数据量大的表里批量插入更新数据的时候,随着插入的数量越来越多,会导致越来越慢,这种情况下,因为我们用的innodb表,可以开启事务, 每次批量执行一批数据更新后提交, 再重新开事务处理下批数据,这样会有效增加效率

还有说明一下: 当我们执行数据库的插入和更新操作很慢的时候,不仅仅是语句,主机性能也很重要, 比如内存和cpu, 如果是虚拟机要相应适当调整, 如果在各种优化了之后效率还是很低, 但cpu和内存的占用却不高,那么就很可能是磁盘的IO性能了,这也会导致数据的更新速度慢。

PHP字符串压缩存入数据库

网上流传这样方法存入压缩数据到mysql:

$data = array();//需要压缩存入数据库的数据

$eventData = addslashes( gzdeflate( json_encode( $data ), 9 ) ); //压缩数据存入数据库

$logData //数据库存入的压缩数据

$eventData = json_decode( gzinflate( $logData ), true );//获取压缩的数据 从数据库读取

实际使用中发现:
$str = “testsaaaaaaddddddd”;
$str1 = gzcompress($str);
$str2 = utf8_encode((gzdeflate($str)));

需要utf8_encode才能存入mysql的规范!

 

[转]MySQL前缀索引和索引选择性

有时候需要索引很长的字符列,这会让索引变得大且慢。通常可以索引开始的部分字符,这样可以大大节约索引空间,从而提高索引效率。但这样也会降低索引的选择性。索引的选择性是指不重复的索引值(也称为基数,cardinality)和数据表的记录总数的比值,范围从1/#T到1之间。索引的选择性越高则查询效率越高,因为选择性高的索引可以让MySQL在查找时过滤掉更多的行。唯一索引的选择性是1,这是最好的索引选择性,性能也是最好的。

一般情况下某个前缀的选择性也是足够高的,足以满足查询性能。对于BLOB,TEXT,或者很长的VARCHAR类型的列,必须使用前缀索引,因为MySQL不允许索引这些列的完整长度。

诀窍在于要选择足够长的前缀以保证较高的选择性,同时又不能太长(以便节约空间)。前缀应该足够长,以使得前缀索引的选择性接近于索引的整个列。换句话说,前缀的”基数“应该接近于完整的列的”基数“。

为了决定前缀的合适长度,需要找到最常见的值的列表,然后和最常见的前缀列表进行比较。下面的示例是mysql官方提供的示例数据库

下载地址如下:

http://downloads.mysql.com/docs/sakila-db.zip

在示例数据库sakila中并没有合适的例子,所以从表city中生成一个示例表,这样就有足够数据进行演示:

复制代码
mysql> select database();                                                           
+------------+
| database() |
+------------+
| sakila     |
+------------+
1 row in set (0.00 sec)

mysql> create table city_demo (city varchar(50) not null);                          
Query OK, 0 rows affected (0.02 sec)

mysql> insert into city_demo (city) select city from city;                          
Query OK, 600 rows affected (0.08 sec)
Records: 600  Duplicates: 0  Warnings: 0

mysql> insert into city_demo (city) select city from city_demo;
Query OK, 600 rows affected (0.07 sec)
Records: 600  Duplicates: 0  Warnings: 0

mysql> update city_demo set city = ( select city from city order by rand() limit 1);
Query OK, 1199 rows affected (0.95 sec)
Rows matched: 1200  Changed: 1199  Warnings: 0

mysql>
复制代码

因为这里使用了rand()函数,所以你的数据会与我的不同,当然那不影响聪明的你。

首先找到最常见的城市列表:

复制代码
mysql> select count(*) as cnt, city from city_demo group by city order by cnt desc limit 10;               
+-----+--------------+
| cnt | city         |
+-----+--------------+
|   8 | Garden Grove |
|   7 | Escobar      |
|   7 | Emeishan     |
|   6 | Amroha       |
|   6 | Tegal        |
|   6 | Lancaster    |
|   6 | Jelets       |
|   6 | Ambattur     |
|   6 | Yingkou      |
|   6 | Monclova     |
+-----+--------------+
10 rows in set (0.01 sec)

mysql>
复制代码

注意到查询结果,上面每个值都出现了6-8次。现在查找到频繁出现的城市前缀。先从3个前缀字母开始,然后4个,5个,6个:

复制代码
mysql> select count(*) as cnt,left(city,3) as pref from city_demo group by pref order by cnt desc limit 10;
+-----+------+
| cnt | pref |
+-----+------+
|  25 | San  |
|  15 | Cha  |
|  12 | Bat  |
|  12 | Tan  |
|  11 | al-  |
|  11 | Gar  |
|  11 | Yin  |
|  10 | Kan  |
|  10 | Sou  |
|  10 | Bra  |
+-----+------+
10 rows in set (0.00 sec)

mysql> select count(*) as cnt,left(city,4) as pref from city_demo group by pref order by cnt desc limit 10; 
+-----+------+
| cnt | pref |
+-----+------+
|  12 | San  |
|  10 | Sout |
|   8 | Chan |
|   8 | Sant |
|   8 | Gard |
|   7 | Emei |
|   7 | Esco |
|   6 | Ying |
|   6 | Amro |
|   6 | Lanc |
+-----+------+
10 rows in set (0.01 sec)

mysql> select count(*) as cnt,left(city,5) as pref from city_demo group by pref order by cnt desc limit 10; 
+-----+-------+
| cnt | pref  |
+-----+-------+
|  10 | South |
|   8 | Garde |
|   7 | Emeis |
|   7 | Escob |
|   6 | Amroh |
|   6 | Yingk |
|   6 | Moncl |
|   6 | Lanca |
|   6 | Jelet |
|   6 | Tegal |
+-----+-------+
10 rows in set (0.01 sec)
复制代码
复制代码
mysql> select count(*) as cnt,left(city,6) as pref from city_demo group by pref order by cnt desc limit 10; 
+-----+--------+
| cnt | pref   |
+-----+--------+
|   8 | Garden |
|   7 | Emeish |
|   7 | Escoba |
|   6 | Amroha |
|   6 | Yingko |
|   6 | Lancas |
|   6 | Jelets |
|   6 | Tegal  |
|   6 | Monclo |
|   6 | Ambatt |
+-----+--------+
10 rows in set (0.00 sec)

mysql>
复制代码

通过上面改变不同前缀长度发现,当前缀长度为6时,这个前缀的选择性就接近完整咧的选择性了。甚至是一样的。

当然还有另外更方便的方法,那就是计算完整列的选择性,并使其前缀的选择性接近于完整列的选择性。下面显示如何计算完整列的选择性:

复制代码
mysql> select count(distinct city) / count(*) from city_demo;
+---------------------------------+
| count(distinct city) / count(*) |
+---------------------------------+
|                          0.4283 |
+---------------------------------+
1 row in set (0.05 sec)

mysql>
复制代码

可以在一个查询中针对不同前缀长度的选择性进行计算,这对于大表非常有用,下面给出如何在同一个查询中计算不同前缀长度的选择性:

复制代码
mysql> select count(distinct left(city,3))/count(*) as sel3,
    -> count(distinct left(city,4))/count(*) as sel4,
    -> count(distinct left(city,5))/count(*) as sel5, 
    -> count(distinct left(city,6))/count(*) as sel6 
    -> from city_demo;
+--------+--------+--------+--------+
| sel3   | sel4   | sel5   | sel6   |
+--------+--------+--------+--------+
| 0.3367 | 0.4075 | 0.4208 | 0.4267 |
+--------+--------+--------+--------+
1 row in set (0.01 sec)

mysql>
复制代码

可以看见当索引前缀为6时的基数是0.4267,已经接近完整列选择性0.4283。

在上面的示例中,已经找到了合适的前缀长度,下面创建前缀索引:

mysql> alter table city_demo add key (city(6));
Query OK, 0 rows affected (0.19 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql>
复制代码
mysql> explain select * from city_demo where city like 'Jinch%';
+----+-------------+-----------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table     | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-----------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | city_demo | range | city          | city | 20      | NULL |    2 | Using where |
+----+-------------+-----------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

mysql>
复制代码

可以看见正确使用刚创建的索引。

前缀索引是一种能使索引更小,更快的有效办法,但另一方面也有其缺点:

mysql无法使用其前缀索引做ORDER BY和GROUP BY,也无法使用前缀索引做覆盖扫描。

[转]MySQL 【去重留一】一条sql语句完成 思路总结

最后在一个技术群里得到了完美的答案,看这条sql语句:

DELETE consum_record
FROM
    consum_record, 
    (
        SELECT
            min(id) id,
            user_id,
            monetary,
            consume_time
        FROM
            consum_record
        GROUP BY
            user_id,
            monetary,
            consume_time
        HAVING
            count(*) > 1
    ) t2
WHERE
    consum_record.user_id = t2.user_id 
    and consum_record.monetary = t2.monetary
    and consum_record.consume_time  = t2.consume_time
AND consum_record.id > t2.id;

上面这条sql语句,仔细看一下,揣摩出思路也不难,大概也分为3步来理解:

  1. (SELECT min(id) id, user_id, monetary, consume_time FROM consum_record GROUP BY user_id, monetary, consume_time HAVING count(*) > 1 ) t2 查询出重复记录形成一个集合(临时表t2),集合里是每种重复记录的最小ID
  2. consum_record.user_id = t2.user_id and consum_record.monetary = t2.monetary and consum_record.consume_time = t2.consume_time 关联判断重复基准的字段
  3. 根据条件,删除原表中id大于t2中id的记录

看到这个语句的时候,心里想这也太厉害了。这么一个简单的sql语句,竟然可以解决这么复杂的问题,涨姿势了~
运行起来也超级快,原先的代码循环执行,需要116s左右,而这里0.3s就可以了,厉害了~

perfect_sql.png

perfect_sql.png