第一部分：看一下分页的基本原理：
第一部分：看一下分页的基本原理：
mysql explain SELECT * FROM message ORDER BY id DESC LIMIT 10000, 20
***************** 1. row **************
id: 1
select_type: SIMPLE
table: message
type: index
possible_keys: NULL
key: PRIMARY
key_len: 4
ref: NULL
rows: 10020
Extra:
1 row in set (0.00 sec) 对上面的mysql语句说明：limit 10000,20的意思扫描满足条件的10020行，扔掉前面的10000行，返回最后的20行，问题就在这里，如果是limit 100000,100，需要扫描100100行，在一个高并发的应用里，每次查询需要扫描超过10W行，性能肯定大打折扣。文中还提到limit n性能是没问题的，因为只扫描n行。
第二部分：根据雅虎的几位工程师带来了一篇Efficient Pagination Using MySQL的报告内容扩展：在文中提到一种clue的做法，给翻页提供一些线索，比如还是SELECT * FROM message ORDER BY id DESC，按id降序分页，每页20条，当前是第10页，当前页条目id最大的是1020，最小的是1000，如果我们只提供上一页、下一页这样的跳转（不提供到第N页的跳转），那么在处理上一页的时候SQL语句可以是：
完整请到：http://www.ityoudao.com/Web/Mysql_606_1349.html
面试时候经常会被问到mysql的索引结构，B+树相较二叉树，红黑树的优势等问题，接下来就分析下这些问题。
首先，让我们先看一张图：
从图中可以看到，我们为 user 表（用户信息表）建立了一个二叉查找树的索引。
图中的圆为二叉查找树的节点，节点中存储了键（key）和数据（data）。键对应 user 表中的 id，数据对应 user 表中的行数据。
二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。
如果我们需要查找 id=12 的用户信息，利用我们创建的二叉查找树索引，查找流程如下：
利用二叉查找树我们只需要 3 次即可找到匹配的数据。如果在表中一条条的查找的话，我们需要 6 次才能找到。
上面我们讲解了利用二叉查找树可以快速的找到数据。但是，如果上面的二叉查找树是这样的构造：
这个时候可以看到我们的二叉查找树变成了一个链表。如果我们需要查找 id=17 的用户信息，我们需要查找 7 次，也就相当于全表扫描了。 导致这个现象的原因其实是二叉查找树变得不平衡了，也就是高度太高了，从而导致查找效率的不稳定。为了解决这个问题，我们需要保证二叉查找树一直保持平衡，就需要用到平衡二叉树了。 平衡二叉树又称 AVL 树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过 1。
下面是平衡二叉树和非平衡二叉树的对比：
由平衡二叉树的构造我们可以发现第一张图中的二叉树其实就是一棵平衡二叉树。
平衡二叉树保证了树的构造是平衡的，当我们插入或删除数据导致不满足平衡二叉树不平衡时，平衡二叉树会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。
因为内存的易失性。一般情况下，我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取 *** 作就会读取更多数据，那我们查找数据的时间也会大幅度降低。如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？
可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低！
为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的 B 树。
B 树（Balance Tree）即为平衡树的意思，下图即是一棵 B 树：
图中的 p 节点为指向子节点的指针，二叉查找树和平衡二叉树其实也有，因为图的美观性，被省略了。
图中的每个节点称为页，页就是我们上面说的磁盘块，在 MySQL 中数据读取的基本单位都是页，所以我们这里叫做页更符合 MySQL 中索引的底层数据结构。
从上图可以看出，B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的 B 树为 3 阶 B 树，高度也会很低。
基于这个特性，B 树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。
假如我们要查找 id=28 的用户信息，那么我们在上图 B 树中查找的流程如下：
B+ 树是对 B 树的进一步优化。让我们先来看下 B+ 树的结构图：
根据上图我们来看下 B+ 树和 B 树有什么不同：
通过上图可以看到，在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。
MyISAM 中的 B+ 树索引实现与 InnoDB 中的略有不同。在 MyISAM 中，B+ 树索引的叶子节点并不存储数据，而是存储数据的文件地址。
摘自： http://www.liuzk.com/410.html
压缩表从名字上来看，简单理解为压缩后的表，也就是把原始表根据一定的压缩算法按照一定的压缩比率压缩后生成的表。
1.1 压缩能力强的产品
表压缩后从磁盘占用上看要比原始表要小很多。如果你熟悉列式数据库，那对这个概念一定不陌生。比如，基于 PostgreSQL 的列式数据库 Greenplum；早期基于 MySQL 的列式数据库 inforbright；或者 Percona 的产品 tokudb 等，都是有压缩能力非常强的数据库产品。
1.2 为什么要用压缩表？
情景一：磁盘大小为 1T，不算其他的空间占用，只能存放 10 张 100G 大小的表。如果这些表以一定的比率压缩后，比如每张表从 100G 压缩到 10G，那同样的磁盘可以存放 100 张表，表的容量是原来的 10 倍。情景二：默认 MySQL 页大小 16K，而 OS 文件系统一般块大小为 4K，所以在 MySQL 在刷脏页的过程中，有一定的概率出现页没写全而导致数据坏掉的情形。比如 16K 的页写了 12K，剩下 4K 没写成功，导致 MySQL 页数据损坏。这个时候就算通过 Redo Log 也恢复不了，因为几乎有所有的关系数据库采用的 Redo Log 都记录了数据页的偏移量，此时就算通过 Redo Log 恢复后，数据也是错误的。所以 MySQL 在刷脏数据之前，会把这部分数据先写入共享表空间里的 DOUBLE WRITE BUFFER 区域来避免这种异常。此时如果 MySQL 采用压缩表，并且每张表页大小和磁盘块大小一致，比如也是 4K，那 DOUBLE WRITE BUFFER 就可以不需要，这部分开销就可以规避掉了。查看文件系统的块大小：
root@ytt-pc:/home/ytt# tune2fs -l /dev/mapper/ytt--pc--vg-root | grep -i 'block size'Block size: 4096
1.3 压缩表的优势
压缩表的优点非常明显，占用磁盘空间小！由于占用空间小，从磁盘置换到内存以及之后经过网络传输都非常节省资源。
简单来讲：节省磁盘 IO，减少网络 IO。
1.4 压缩表的缺陷当然压缩表也有缺点，压缩表的写入（INSERT,UPDATE,DELETE）比普通表要消耗更多的 CPU 资源。
压缩表的写入涉及到解压数据，更新数据，再压缩数据，比普通表多了解压和再压缩两个步骤，压缩和解压缩需要消耗一定的 CPU 资源。所以需要选择一个比较优化的压缩算法。
1.5 MySQL 支持的压缩算法这块是 MySQL 所有涉及到压缩的基础，不仅仅用于压缩表，也用于其它地方。比如客户端请求到 MySQL 服务端的数据压缩；主从之间的压缩传输；利用克隆插件来复制数据库 *** 作的压缩传输等等。
从下面结果可以看到 MySQL 支持的压缩算法为 zlib 和 zstd，MySQL 默认压缩算法为 zlib，当然你也可以选择非 zlib 算法，比如 zstd。至于哪种压缩算法最优，暂时没办法简单量化，依赖表中的数据分布或者业务请求。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）