MySql基础

关系数据库概念

• 关系型数据库就是一种建立在关系模型的基础上的数据库。关系模型表明了数据库中所存储的数据之间的联系（一对一、一对多、多对多）。关系型数据库中，我们的数据都被存放在了各种表中（比如用户表），表中的每一行就存放着一条数据（比如一个用户的信息）。
• 大部分关系型数据库都使用 SQL 来操作数据库中的数据。并且，大部分关系型数据库都支持事务的四大特性(ACID)。
  有哪些常见的关系型数据库呢？
  MySQL、PostgreSQL、Oracle、SQL Server、SQLite（微信本地的聊天记录的存储就是用的 SQLite）

MyISAM 和 InnoDB 的区别

• MySQL 5.5 之前，MyISAM 引擎是 MySQL 的默认存储引擎，5.5 版本之后，MySQL 引入了 InnoDB（事务性数据库引擎），MySQL 5.5 版本后默认的存储引擎为 InnoDB。
• 两者对比：
  • 锁：MyISAM 只有表级锁(table-level locking)，而 InnoDB 支持行级锁(row-level locking)和表级锁,默认为行级锁。
  • 事务：MyISAM 不提供事务支持；InnoDB 提供事务支持，具有提交(commit)和回滚(rollback)事务的能力。
  • 外键：MyISAM 不支持，而 InnoDB 支持。
  • 恢复：MyISAM 不支持数据库异常崩溃后的安全恢复，而 InnoDB 支持。
  • MVCC：MyISAM 不支持，而 InnoDB 支持。
  • 速度： 不要轻易相信“MyISAM 比 InnoDB 快”之类的经验之谈，这个结论往往不是绝对的。在很多我们已知场景中，InnoDB 的速度都可以让 MyISAM 望尘莫及，尤其是用到了聚簇索引，或者需要访问的数据都可以放入内存的应用。————《MySQL 高性能》

拓展一下

• 一般我们也是不建议在数据库层面使用外键的，应用层面可以解决。不过，这样会对数据的一致性造成威胁。具体要不要使用外键还是要根据你的项目来决定。
• MySQL InnoDB 引擎使用 redo log(重做日志) 保证事务的持久性，使用 undo log(回滚日志) 来保证事务的原子性。
• MySQL InnoDB 引擎通过 锁机制、MVCC 等手段来保证事务的隔离性（ 默认支持的隔离级别是 REPEATABLE-READ ）。
• 保证了事务的持久性、原子性、隔离性之后，一致性才能得到保障。
• MVCC 可以看作是行级锁的一个升级，可以有效减少加锁操作，提供性能。

因此，对于咱们日常开发的业务系统来说，你几乎找不到什么理由再使用 MyISAM 作为自己的 MySQL 数据库的存储引擎。

锁机制与 InnoDB 锁算法

MyISAM 和 InnoDB 存储引擎使用的锁

• MyISAM 采用表级锁(table-level locking)。
• InnoDB 支持行级锁(row-level locking)和表级锁,默认为行级锁

表级锁和行级锁对比

• 表级锁： MySQL 中锁定粒度最大的一种锁，对当前操作的整张表加锁，实现简单，资源消耗也比较少，加锁快，不会出现死锁。其锁定粒度最大，触发锁冲突的概率最高，并发度最低，MyISAM 和 InnoDB 引擎都支持表级锁。
• 行级锁： MySQL 中锁定粒度最小的一种锁，只针对当前操作的行进行加锁。行级锁能大大减少数据库操作的冲突。其加锁粒度最小，并发度高，但加锁的开销也最大，加锁慢，会出现死锁。
• 页面锁：开销和加锁时间界于表锁和行锁之间；会出现死锁；锁定粒度界于表锁和行锁之间，并发度一般

InnoDB 存储引擎的锁的算法有三种

• Record lock：记录锁，单个行记录上的锁
• Gap lock：间隙锁，锁定一个范围，不包括记录本身
• Next-key lock：record+gap 临键锁，锁定一个范围，包含记录本身

死锁

表级锁不会产生死锁，所以解决死锁主要还是针对于最常用的InnoDB。

mysql死锁的关键在于：两个(或以上)的Session加锁的顺序不一致。

那么对应的解决死锁问题的关键就是：让不同的session加锁有次序

举例1
例如两个用户同时投资，A用户金额随机分为2份，分给借款人1，2

B用户金额随机分为2份，分给借款人2，1

由于加锁的顺序不一样，死锁当然很快就出现了。

对于这个问题的改进很简单，直接把所有分配到的借款人直接一次锁住就行了。

Select * from xxx where id in (xx,xx,xx) for update

在in里面的列表值mysql是会自动从小到大排序，加锁也是一条条从小到大加的锁

举例2
在开发中，经常会做这类的判断需求：根据字段值查询（有索引），如果不存在，则插入；否则更新。

以id为主键为例，目前还没有id=22的行

# session1:
select * from t3 where id=22 for update;
Empty set (0.00 sec)
# session2:
select * from t3 where id=23  for update;
Empty set (0.00 sec)
# session1:
insert into t3 values(22,'ac','a',now());
# 锁等待中……
# session2:
insert into t3 values(23,'bc','b',now());
# ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

当对存在的行进行锁的时候(主键)，mysql就只有行锁。

当对未存在的行进行锁的时候(即使条件为主键)，mysql是会锁住一段范围（有gap锁）

锁住的范围为：

(无穷小或小于表中锁住id的最大值，无穷大或大于表中锁住id的最小值)

对于这种死锁的解决办法是：

insert into t3(xx,xx) on duplicate key updatexx='XX';

一般的情况，两个session分别通过一个sql持有一把锁，然后互相访问对方加锁的数据产生死锁。
两个单条的sql语句涉及到的加锁数据相同，但是加锁顺序不同，导致了死锁。

死锁预防策略

InnoDB引擎内部(或者说是所有的数据库内部)，有多种锁类型：事务锁(行锁、表锁)，Mutex(保护内部的共享变量操作)、RWLock(又称之为Latch，保护内部的页面读取与修改)。

InnoDB每个页面为16K，读取一个页面时，需要对页面加S锁，更新一个页面时，需要对页面加上X锁。

任何情况下，操作一个页面，都会对页面加锁，页面锁加上之后，页面内存储的索引记录才不会被并发修改。

因此，为了修改一条记录，InnoDB内部如何处理：

• 根据给定的查询条件，找到对应的记录所在页面；

• 对页面加上X锁(RWLock)，然后在页面内寻找满足条件的记录；

• 在持有页面锁的情况下，对满足条件的记录加事务锁(行锁：根据记录是否满足查询条件，记录是否已经被删除，分别对应于上面提到的3种加锁策略之一)；

相对于事务锁，页面锁是一个短期持有的锁，而事务锁(行锁、表锁)是长期持有的锁。

因此，为了防止页面锁与事务锁之间产生死锁。InnoDB做了死锁预防的策略：持有事务锁(行锁、表锁)，可以等待获取页面锁；但反之，持有页面锁，不能等待持有事务锁。

根据死锁预防策略，在持有页面锁，加行锁的时候，如果行锁需要等待,则释放页面锁，然后等待行锁。

此时，行锁获取没有任何锁保护，因此加上行锁之后，记录可能已经被并发修改。

因此，此时要重新加回页面锁，重新判断记录的状态，重新在页面锁的保护下，对记录加锁。

如果此时记录未被并发修改，那么第二次加锁能够很快完成，因为已经持有了相同模式的锁。

但是，如果记录已经被并发修改，那么，就有可能导致本文前面提到的死锁问题。

MySQL死锁产生原因和解决方法

查询缓存

• 执行查询语句的时候，会先查询缓存。不过，MySQL 8.0 版本后移除，因为这个功能不太实用。
• 开启查询缓存后在同样的查询条件以及数据情况下，会直接在缓存中返回结果。这里的查询条件包括查询本身、当前要查询的数据库、客户端协议版本号等一些可能影响结果的信息。因此任何两个查询在任何字符上的不同都会导致缓存不命中。此外，如果查询中包含任何用户自定义函数、存储函数、用户变量、临时表、MySQL 库中的系统表，其查询结果也不会被缓存。
• 缓存建立之后，MySQL 的查询缓存系统会跟踪查询中涉及的每张表，如果这些表（数据或结构）发生变化，那么和这张表相关的所有缓存数据都将失效。
• 缓存虽然能够提升数据库的查询性能，但是缓存同时也带来了额外的开销，每次查询后都要做一次缓存操作，失效后还要销毁。 因此，开启查询缓存要谨慎，尤其对于写密集的应用来说更是如此。如果开启，要注意合理控制缓存空间大小，一般来说其大小设置为几十 MB 比较合适。

事务

• 概念：事务是逻辑上的一组操作，要么都执行，要么都不执行。平时，我们在谈论事务的时候，如果没有特指分布式事务，往往指的就是数据库事务。
• ACID：
  • 原子性（Atomicity） ： 事务是最小的执行单位，不允许分割。事务的原子性确保动作要么全部完成，要么完全不起作用；
  • 一致性（Consistency）： 执行事务前后，数据保持一致，例如转账业务中，无论事务是否成功，转账者和收款人的总额应该是不变的；
• 隔离性（Isolation）： 并发访问数据库时，一个用户的事务不被其他事务所干扰，各并发事务之间数据库是独立的；
• 持久性（Durabilily）： 一个事务被提交之后。它对数据库中数据的改变是持久的，即使数据库发生故障也不应该对其有任何影响。

数据事务的实现原理呢？

• 我们这里以 MySQL 的 InnoDB 引擎为例来简单说一下。
• MySQL InnoDB 引擎使用redo log(重做日志)保证事务的持久性，使用undo log(回滚日志)来保证事务的原子性。
• MySQL InnoDB 引擎通过锁机制、MVCC等手段来保证事务的隔离性（ 默认支持的隔离级别是 REPEATABLE-READ ）。
• 保证了事务的持久性、原子性、隔离性之后，一致性才能得到保障。

并发事务带来哪些问题

• 脏读（Dirty read）: 当一个事务正在访问数据并且对数据进行了修改，而这种修改还没有提交到数据库中，这时另外一个事务也访问了这个数据，然后使用了这个数据。因为这个数据是还没有提交的数据，那么另外一个事务读到的这个数据是“脏数据”，依据“脏数据”所做的操作可能是不正确的。
• 丢失修改（Lost to modify）: 指在一个事务读取一个数据时，另外一个事务也访问了该数据，那么在第一个事务中修改了这个数据后，第二个事务也修改了这个数据。这样第一个事务内的修改结果就被丢失，因此称为丢失修改。 例如：事务 1 读取某表中的数据 A=20，事务 2 也读取 A=20，事务 1 修改 A=A-1，事务 2 也修改 A=A-1，最终结果 A=19，事务 1 的修改被丢失。
• 不可重复读（Unrepeatable read）: 指在一个事务内多次读同一数据。在这个事务还没有结束时，另一个事务也访问该数据。那么，在第一个事务中的两次读数据之间，由于第二个事务的修改导致第一个事务两次读取的数据可能不太一样。这就发生了在一个事务内两次读到的数据是不一样的情况，因此称为不可重复读。
• 幻读（Phantom read）: 幻读与不可重复读类似。它发生在一个事务（T1）读取了几行数据，接着另一个并发事务（T2）插入了一些数据时。在随后的查询中，第一个事务（T1）就会发现多了一些原本不存在的记录，就好像发生了幻觉一样，所以称为幻读。
  不可重复读和幻读区别
• 不可重复读的重点是修改比如多次读取一条记录发现其中某些列的值被修改，幻读的重点在于新增或者删除比如多次读取一条记录发现记录增多或减少了。

SQL 标准定义了四个隔离级别

• READ-UNCOMMITTED(读取未提交)： 最低的隔离级别，允许读取尚未提交的数据变更，可能会导致脏读、幻读或不可重复读。
• READ-COMMITTED(读取已提交)： 允许读取并发事务已经提交的数据，可以阻止脏读，但是幻读或不可重复读仍有可能发生。
• REPEATABLE-READ(可重复读)： 对同一字段的多次读取结果都是一致的，除非数据是被本身事务自己所修改，可以阻止脏读和不可重复读，但幻读仍有可能发生。
  MySQL InnoDB 的 REPEATABLE-READ（可重读）并不保证避免幻读，需要应用使用加锁读来保证。而这个加锁度使用到的机制就是 Next-Key Locks。
• SERIALIZABLE(可串行化)： 最高的隔离级别，完全服从 ACID 的隔离级别。所有的事务依次逐个执行，这样事务之间就完全不可能产生干扰，也就是说，该级别可以防止脏读、不可重复读以及幻读。

MySQL 的默认隔离级别

• MySQL InnoDB 存储引擎的默认支持的隔离级别是 REPEATABLE-READ（可重读）。我们可以通过SELECT @@tx_isolation;命令来查看，MySQL 8.0 该命令改为SELECT @@transaction_isolation;
• 因为隔离级别越低，事务请求的锁越少，所以大部分数据库系统的隔离级别都是 READ-COMMITTED(读取提交内容) ，但是你要知道的是 InnoDB 存储引擎默认使用REPEATABLE-READ（可重读）并不会有任何性能损失。
• InnoDB 存储引擎在 分布式事务 的情况下一般会用到 SERIALIZABLE(可串行化) 隔离级别。

InnoDB 存储引擎提供了对 XA 事务的支持，并通过 XA 事务来支持分布式事务的实现。分布式事务指的是允许多个独立的事务资源（transactional resources）参与到一个全局的事务中。事务资源通常是关系型数据库系统，但也可以是其他类型的资源。全局事务要求在其中的所有参与的事务要么都提交，要么都回滚，这对于事务原有的 ACID 要求又有了提高。另外，在使用分布式事务时，InnoDB 存储引擎的事务隔离级别必须设置为 SERIALIZABLE。————《MySQL 技术内幕：InnoDB 存储引擎(第 2 版)》7.7 章

索引

概念

• 索引是一种用于快速查询和检索数据的数据结构。常见的索引结构有: B 树， B+树和 Hash
• 索引的作用就相当于目录的作用。打个比方: 我们在查字典的时候，如果没有目录，那我们就只能一页一页的去找我们需要查的那个字，速度很慢。如果有目录了，我们只需要先去目录里查找字的位置，然后直接翻到那一页就行了。

索引的优缺点

优点

• 使用索引可以大大加快数据的检索速度（大大减少检索的数据量）, 这也是创建索引的最主要的原因。
• 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。

  缺点

• 创建索引和维护索引需要耗费许多时间。当对表中的数据进行增删改的时候，如果数据有索引，那么索引也需要动态的修改，会降低 SQL 执行效率。
• 索引需要使用物理文件存储，也会耗费一定空间。

大多数情况下，索引查询都是比全表扫描要快的。但是如果数据库的数据量不大，那么使用索引也不一定能够带来很大提升。

索引的底层数据结构

Hash表 & B+树

• 哈希表是键值对的集合（通过哈希算法），通过键(key)即可快速取出对应的值(value)，因此哈希表可以快速检索数据（接近 O（1））。
  
• 哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前HashMap就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。
  
• 为了减少 Hash 冲突的发生，一个好的哈希函数应该“均匀地”将数据分布在整个可能的哈希值集合中。

为什么MySQL 没有使用其作为索引的数据结构？

• Hash 冲突问题 ：我们上面也提到过Hash 冲突了，不过对于数据库来说这还不算最大的缺点。
• Hash 索引不支持顺序和范围查询(Hash 索引不支持顺序和范围查询是它最大的缺点： 假如我们要对表中的数据进行排序或者进行范围查询，那 Hash 索引可就不行了。）
• 为什么不适用红黑树：数高决定了磁盘io次数
• 为什么不使用跳表：跳表的空间复杂度为 o(n)，跳表的查询的时间复杂度为 O(logn），插入和删除的时间复杂度也为 O(longn)，（Redis是 内存中读取数据，不涉及IO，因此使用了跳表），跳表每级遍历 3 个结点即可，而跳表的高度为 h ，所以每次查找一个结点时，需要遍历的结点数为 3*跳表高度

B 树& B+树

• B 树也称 B-树,全称为多路平衡查找树，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。
• 目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。

  B 树& B+树两者有何异同

• B 树的所有节点既存放键(key) 也存放 数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
• B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
• B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
• 在B树保持树的平衡的过程中，每次关键字的变化都会导致机构发生很大的变化，这个过程是特别浪费时间的，所以创建索引一定要创建合适的索引，而不是把所有的字段都建立索引，创建冗余的索引只会对数据的增加、删除、修改增加更大的性能消耗。
  
• 在 MySQL 中，MyISAM 引擎和 InnoDB 引擎都是使用 B+Tree 作为索引结构，但是，两者的实现方式不太一样。
• MyISAM 引擎中，B+Tree 叶节点的 data 域存放的是数据记录的地址。在索引检索的时候，首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址读取相应的数据记录。这被称为“非聚簇索引”。
• InnoDB 引擎中，其数据文件本身就是索引文件。相比 MyISAM，索引文件和数据文件是分离的，其表数据文件本身就是按 B+Tree 组织的一个索引结构，树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。这被称为“聚簇索引（或聚集索引）”，而其余的索引都作为辅助索引，辅助索引的 data 域存储相应记录主键的值而不是地址，这也是和 MyISAM 不同的地方。在根据主索引搜索时，直接找到 key 所在的节点即可取出数据；在根据辅助索引查找时，则需要先取出主键的值，在走一遍主索引。 因此，在设计表的时候，不建议使用过长的字段作为主键，也不建议使用非单调的字段作为主键，这样会造成主索引频繁分裂。

总结

Mysql为什么最终选择了B+树作为索引的数据结构

• B树能解决的问题，B+树都能解决，且能够更好的解决，降低了树的高度，增加节点的数据存储量。
• B+树的扫库和扫表能力更强，如果根据索引去根据数据表扫描，对B树扫描，需要整颗树遍历，B+树只需要遍历所有的叶子节点
• B+树的磁盘读写能力更强，根结点和支节点不保存数据区，所有的根结点和支节点天同样大小的情况下，保存的关键字更多，叶子结点不存子节点的引用，所以，B+树读写一次磁盘加载的关键字更多
• B+树具有天然的排序功能
• B+树的查询效率更加稳定，每次查询数据，查询IO次数是稳定的。

索引类型

主键索引(Primary Key)

• 数据表的主键列使用的就是主键索引。
• 一张数据表有只能有一个主键，并且主键不能为 null，不能重复。
• 在 MySQL 的 InnoDB 的表中，当没有显示的指定表的主键时，InnoDB 会自动先检查表中是否有唯一索引的字段，如果有，则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个 6Byte 的自增主键。

二级索引(辅助索引)

二级索引又称为辅助索引，是因为二级索引的叶子节点存储的数据是主键。也就是说，通过二级索引，可以定位主键的位置。唯一索引，普通索引，前缀索引等索引属于二级索引。

• 唯一索引(Unique Key)：唯一索引也是一种约束。唯一索引的属性列不能出现重复的数据，但是允许数据为 NULL，一张表允许创建多个唯一索引。 建立唯一索引的目的大部分时候都是为了该属性列的数据的唯一性，而不是为了查询效率。
• 普通索引(Index)：普通索引的唯一作用就是为了快速查询数据，一张表允许创建多个普通索引，并允许数据重复和 NULL。
• 前缀索引(Prefix)：前缀索引只适用于字符串类型的数据。前缀索引是对文本的前几个字符创建索引，相比普通索引建立的数据更小， 因为只取前几个字符。
• 全文索引(Full Text)：全文索引主要是为了检索大文本数据中的关键字的信息，是目前搜索引擎数据库使用的一种技术。Mysql5.6 之前只有 MYISAM 引擎支持全文索引，5.6 之后 InnoDB 也支持了全文索引。
  

聚集索引与非聚集索引

聚集索引

• 聚集索引即索引结构和数据一起存放的索引。主键索引属于聚集索引。
• 在 Mysql 中，InnoDB 引擎的表的 .ibd文件就包含了该表的索引和数据，对于 InnoDB 引擎表来说，该表的索引(B+树)的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据。
• 优点：聚集索引的查询速度非常的快，因为整个 B+树本身就是一颗多叉平衡树，叶子节点也都是有序的，定位到索引的节点，就相当于定位到了数据。
• 缺点：依赖于有序的数据：因为B+树是多路平衡树，如果索引的数据不是有序的，那么就需要在插入时排序，如果数据是整型还好，否则类似于字符串或 UUID 这种又长又难比较的数据，插入或查找的速度肯定比较慢。
• 更新代价大： 如果对索引列的数据被修改时，那么对应的索引也将会被修改， 而且况聚集索引的叶子节点还存放着数据，修改代价肯定是较大的， 所以对于主键索引来说，主键一般都是不可被修改的。

非聚集索引

• 非聚集索引即索引结构和数据分开存放的索引。二级索引属于非聚集索引。
  MYISAM引擎的表的.MYI 文件包含了表的索引，该表的索引(B+树)的每个叶子非叶子节点存储索引，叶子节点存储索引和索引对应数据的指针，指向.MYD 文件的数据。
• 优点：更新代价比聚集索引要小。非聚集索引的更新代价就没有聚集索引那么大了，非聚集索引的叶子节点是不存放数据的。
• 缺点：
  • 跟聚集索引一样，非聚集索引也依赖于有序的数据。
  • 可能会二次查询(回表):这应该是非聚集索引最大的缺点了。 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。(回表的操作更多的是随机io,随机io在性能上还是比较低)

随机IO：假设我们所需要的数据是随机分散在磁盘的不同页的不同扇区中的，那么找到相应的数据需要等到磁臂（寻址作用）旋转到指定的页，然后盘片寻找到对应的扇区，才能找到我们所需要的一块数据，一次进行此过程直到找完所有数据，这个就是随机IO，读取数据速度较慢。
顺序IO：假设我们已经找到了第一块数据，并且其他所需的数据就在这一块数据后边，那么就不需要重新寻址，可以依次拿到我们所需的数据，这个就叫顺序IO

• 这是 MySQL 的表的文件截图:
  
• 聚集索引和非聚集索引:
  

非聚集索引一定回表查询吗(覆盖索引)

非聚集索引不一定回表查询

# 用户准备使用 SQL 查询用户名，而用户名字段正好建立了索引。
 SELECT name FROM table WHERE name='guang19';
# 那么这个索引的 key 本身就是 name，查到对应的 name 直接返回就行了，无需回表查询。

• 即使是 MYISAM 也是这样，虽然 MYISAM 的主键索引确实需要回表， 因为它的主键索引的叶子节点存放的是指针。但是如果 SQL 查的就是主键呢?

  SELECT id FROM table WHERE id=1;

• 主键索引本身的 key 就是主键，查到返回就行了。这种情况就称之为覆盖索引了。

覆盖索引

• 如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”。
• 我们知道在 InnoDB 存储引擎中，如果不是主键索引，叶子节点存储的是主键+列值。最终还是要“回表”，也就是要通过主键再查找一次。这样就会比较慢覆盖索引就是把要查询出的列和索引是对应的，不做回表操作！
• 覆盖索引即需要查询的字段正好是索引的字段，那么直接根据该索引，就可以查到数据了， 而无需回表查询。
  如主键索引，如果一条 SQL 需要查询主键，那么正好根据主键索引就可以查到主键。
  再如普通索引，如果一条 SQL 需要查询 name，name 字段正好有索引， 那么直接根据这个索引就可以查到数据，也无需回表。
  

磁盘io次数

数据量小的话，直接把索引放到内存中，内存的O(logn)消耗是远远低于磁盘io的,所以可以忽略不计

数据量大的话，采用索引结构，我们这部分先从二叉树说起，对于普通二叉树，第一个步骤是二分，每次判断都是一次半数的数量级检索。假如有100W的数据，大概的时间复杂度是：log2N=1000000即N=20的节点获取，也就是磁盘I/O复杂度最大为O(20)，二分的时间复杂度是O(log2N)。

但是对于数据库来说，存储场景会更加复杂，二叉树的性能虽然好，但我们还是想要树的高度更低一些，存储的数据更多一些。因此mysql引入了B+树的概念。除了根节点之外，第二层级的数量得到了充分的扩展，相对于普通的二叉树，B+树的结构更加庞大又不失美感。

假设非叶节点不同元素占用情况为：下一条记录指针占4Byte，id值8Byte，目标记录指针4Byte，那么一个4Kb的磁盘块将大致可以容纳250个下级指针，100万行目标记录(假设叶子节点也是只保存了id值，则一个非叶子节点下面也包括大概250个叶子节点)只需log250N=1000000即N=3的I/O次数，充分提升了每次节点I/O带来的检索效用，时间复杂度是O（lognN）,这里的n是非叶子结点的个数。（PS：实际上innodb的数据页大小是16kb，这个n会更大，那么对应的，io次数也会更少）

在实际的查询中，IO次数可能会更小，因为有可能会把部分用到的索引读取到内存中，相对于磁盘IO来说，内存的io消耗可以忽略不计。

一般来说B+Tree的高度一般都在2-4层，MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作（根节点的那次不算磁盘I/O）。

最左原则

最左匹配原则就是指在联合索引中，如果你的 SQL 语句中用到了联合索引中的最左边的索引，那么这条 SQL 语句就可以利用这个联合索引去进行匹配。例如某表现有索引(a,b,c)，现在你有如下语句：

select * from t where a=1 and b=1 and c =1;     #这样可以利用到定义的索引（a,b,c）,用上a,b,c
select * from t where a=1 and b=1;     #这样可以利用到定义的索引（a,b,c）,用上a,b
select * from t where b=1 and a=1;     #这样可以利用到定义的索引（a,b,c）,用上a,c（mysql有查询优化器）
select * from t where a=1;     #这样也可以利用到定义的索引（a,b,c）,用上a
select * from t where b=1 and c=1;     #这样不可以利用到定义的索引（a,b,c）
select * from t where a=1 and c=1;     #这样可以利用到定义的索引（a,b,c），但只用上a索引，b,c索引用不到

也就是说通过最左匹配原则你可以定义一个联合索引，使得多种查询条件都可以用到该索引。
值得注意的是，当遇到范围查询(>、<、between、like)就会停止匹配。也就是：

select * from t where a=1 and b>1 and c =1; #这样a,b可以用到（a,b,c），c索引用不到 

像select * from table where a = '1' and b > ‘2’ and c='3'这种类型的sql语句，在a、b走完索引后，c肯定是无序了，所以c就没法走索引，数据库会觉得还不如全表扫描c字段来的快。

以index （a,b,c）为例建立这样的索引相当于建立了索引a、ab、abc三个索引。一个索引顶三个索引当然是好事，毕竟每多一个索引，都会增加写操作的开销和磁盘空间的开销。

最左匹配原则的原理
联合索引的叶子节点键值数量不是一个，而是多个。

由于构建一颗 B+ 树只能根据一个值来构建，因此数据库依据联合索引最左的字段来构建 B+ 树。

该图就是一个形如(a,b,c)联合索引的 b+ 树，其中的非叶子节点存储的是第一个关键字的索引 a，而叶子节点存储的是三个关键字的数据。

这里可以看出 a 是有序的，而 b，c 都是无序的。但是当在 a 相同的时候，b 是有序的，b 相同的时候，c 又是有序的。

总结

• 在 InnoDB 中联合索引只有先确定了前一个（左侧的值）后，才能确定下一个值。如果有范围查询的话，那么联合索引中使用范围查询的字段后的索引在该条 SQL 中都不会起作用。

• 值得注意的是，in 和 = 都可以乱序，比如有索引（a,b,c），语句 select * from t where c =1 and a=1 and b=1，这样的语句也可以用到最左匹配，因为 MySQL 中有一个优化器，他会分析 SQL 语句，将其优化成索引可以匹配的形式，即 select * from t where a =1 and a=1 and c=1

联合索引的优点

• 减少开销：建一个联合索引(col1,col2,col3)，实际相当于建了(col1),(col1,col2),(col1,col2,col3)三个索引。每多一个索引，都会增加写操作的开销和磁盘空间的开销。对于大量数据的表，使用联合索引会大大的减少开销
• 覆盖索引。对联合索引(col1,col2,col3)，如果有如下的sql: select col1,col2,col3 from test where col1=1 and col2=2。那么MySQL可以直接通过遍历索引取得数据，而无需回表，这减少了很多的随机io操作。减少io操作，特别的随机io其实是dba主要的优化策略。所以，在真正的实际应用中，覆盖索引是主要的提升性能的优化手段之一。
• 效率高。索引列越多，通过索引筛选出的数据越少。

创建索引的注意事项

选择合适的字段创建索引

• 不为NULL的字段：索引字段的数据应该尽量不为 NULL，因为对于数据为 NULL 的字段，数据库较难优化。如果字段频繁被查询，但又避免不了为 NULL，建议使用 0,1,true,false 这样语义较为清晰的短值或短字符作为替代。
• 被频繁查询的字段：我们创建索引的字段应该是查询操作非常频繁的字段。
• 被作为条件查询的字段：被作为 WHERE 条件查询的字段，应该被考虑建立索引。
• 频繁需要排序的字段：索引已经排序，这样查询可以利用索引的排序，加快排序查询时间。
• 被经常频繁用于连接的字段：经常用于连接的字段可能是一些外键列，对于外键列并不一定要建立外键，只是说该列涉及到表与表的关系。对于频繁被连接查询的字段，可以考虑建立索引，提高多表连接查询的效率。

选择合适的字段创建索引

• 虽然索引能带来查询上的效率，但是维护索引的成本也是不小的。 如果一个字段不被经常查询，反而被经常修改，那么就更不应该在这种字段上建立索引了。

尽可能的考虑建立联合索引而不是单列索引

• 因为索引是需要占用磁盘空间的，可以简单理解为每个索引都对应着一颗 B+树。如果一个表的字段过多，索引过多，那么当这个表的数据达到一个体量后，索引占用的空间也是很多的，且修改索引时，耗费的时间也是较多的。如果是联合索引，多个字段在一个索引上，那么将会节约很大磁盘空间，且修改数据的操作效率也会提升。

注意避免冗余索引

• 冗余索引指的是索引的功能相同，能够命中索引(a, b)就肯定能命中索引(a) ，那么索引(a)就是冗余索引。如（name,city ）和（name ）这两个索引就是冗余索引，能够命中前者的查询肯定是能够命中后者的 在大多数情况下，都应该尽量扩展已有的索引而不是创建新索引。

考虑在字符串类型的字段上使用前缀索引代替普通索引

• 前缀索引仅限于字符串类型，较普通索引会占用更小的空间，所以可以考虑使用前缀索引带替普通索引。

使用索引的一些建议

• 对于中到大型表索引都是非常有效的，但是特大型表的话维护开销会很大，不适合建索引。
• 避免 where 子句中对字段施加函数，这会造成无法命中索引。
• 在使用 InnoDB 时使用与业务无关的自增主键作为主键，即使用逻辑主键，而不要使用业务主键。
• 删除长期未使用的索引，不用的索引的存在会造成不必要的性能损耗 MySQL 5.7 可以通过查询 sys 库的 schema_unused_indexes 视图来查询哪些索引从未被使用。
• 在使用 limit offset 查询缓慢时，可以借助索引来提高性能。

建立索引SQL

# 添加 PRIMARY KEY（主键索引）
ALTER TABLE `table_name` ADD PRIMARY KEY ( `column` )
# 添加 UNIQUE(唯一索引)
ALTER TABLE `table_name` ADD UNIQUE ( `column` )
# 添加 INDEX(普通索引)
ALTER TABLE `table_name` ADD INDEX index_name ( `column` )
# 添加 FULLTEXT(全文索引)
ALTER TABLE `table_name` ADD FULLTEXT ( `column`)
# 添加多列索引
ALTER TABLE `table_name` ADD INDEX index_name ( `column1`, `column2`, `column3` )

MySQL 高性能优化规范建议

数据库命令规范

• 所有数据库对象名称必须使用小写字母并用下划线分割
• 所有数据库对象名称禁止使用 MySQL 保留关键字（如果表名中包含关键字查询时，需要将其用单引号括起来）
• 数据库对象的命名要能做到见名识意，并且最后不要超过32个字符
• 临时库表必须以 tmp_为前缀并以日期为后缀，备份表必须以 bak_为前缀并以日期 (时间戳) 为后缀
• 所有存储相同数据的列名和列类型必须一致（一般作为关联列，如果查询时关联列类型不一致会自动进行数据类型隐式转换，会造成列上的索引失效，导致查询效率降低）

数据库基本设计规范

所有表必须使用 Innodb 存储引擎

• 没有特殊要求（即 Innodb 无法满足的功能如：列存储，存储空间数据等）的情况下，所有表必须使用 Innodb 存储引擎（MySQL5.5 之前默认使用 Myisam，5.6 以后默认的为 Innodb）。
• Innodb 支持事务，支持行级锁，更好的恢复性，高并发下性能更好。

阿里巴巴开发手册数据库部分的一些最佳实践

模糊查询

• 【强制】页面搜索严禁左模糊或者全模糊，如果需要请走搜索引擎来解决。
  （说明:索引文件具有 B-Tree 的最左前缀匹配特性，如果左边的值未确定，那么无法使用此索引。）

外键和级联

• 【强制】不得使用外键与级联，一切外键概念必须在应用层解决。
  （说明:以学生和成绩的关系为例，学生表中的 student_id 是主键，那么成绩表中的 student_id 则为外键。如果更新学生表中的 student_id，同时触发成绩表中的 student_id 更新，即为级联更新。外键与级联更新适用于单机低并发，不适合分布式、高并发集群;级联更新是强阻塞，存在数据库更新风暴的风险;外键影响数据库的插入速度）

  关于@Transactional注解

• @Transactional事务不要滥用。事务会影响数据库的QPS，另外使用事务的地方需要考虑各方面的回滚方案，包括缓存回滚、搜索引擎回滚、消息补偿、统计修正等。

Tips:

• InnoDB默认的行锁可以使得操作不同行时不会产生相互影响、不会阻塞，从而很好的解决了多事务和并发的问题。但是，那得基于一个前提，即 Where 条件中使用上了索引；反之，如果没有使用上索引，则是全表扫描、全部阻塞。
  即当 Where 查询条件中的字段没有索引时，更新操作会锁住全表！即加表锁

MVCC

一致性非锁定读和锁定读

一致性非锁定读

对于 一致性非锁定读（Consistent Nonlocking Reads） 的实现，通常做法是加一个版本号或者时间戳字段，在更新数据的同时版本号 + 1 或者更新时间戳。
查询时，将当前可见的版本号与对应记录的版本号进行比对，如果记录的版本小于可见版本，则表示该记录可见

在 InnoDB 存储引擎中，多版本并发控制 (Multiversion Concurrency Control) 就是对非锁定读的实现。

如果读取的行正在执行 DELETE 或 UPDATE 操作，这时读取操作不会去等待行上锁的释放。相反地，InnoDB 存储引擎会去读取行的一个快照数据，对于这种读取历史数据的方式，我们叫它快照读 (snapshot read)

在 Repeatable Read 和 Read Committed 两个隔离级别下，如果是执行普通的 select 语句则会使用 一致性非锁定读（MVCC）。并且在 Repeatable Read 下 MVCC 实现了可重复读和防止部分幻读

锁定读

如果执行的是下列语句，就是 锁定读（Locking Reads）

• select ... lock in share mode
• select ... for update
• insert、update、delete

在锁定读下，读取的是数据的最新版本，这种读也被称为 当前读（current read）。锁定读会对读取到的记录加锁：

• select ... lock in share mode：对记录加 S 锁，其它事务也可以加S锁，如果加 x 锁则会被阻塞
• select ... for update、insert、update、delete：对记录加 X 锁，且其它事务不能加任何锁

在一致性非锁定读下，即使读取的记录已被其它事务加上 X 锁，这时记录也是可以被读取的，即读取的快照数据。

上面说了，在 Repeatable Read 下 MVCC 防止了部分幻读，这边的 “部分” 是指在 一致性非锁定读 情况下，只能读取到第一次查询之前所插入的数据（根据 Read View 判断数据可见性，Read View 在第一次查询时生成）。

但是！如果是 当前读 ，每次读取的都是最新数据，这时如果两次查询中间有其它事务插入数据，就会产生幻读。

所以， InnoDB 在实现 Repeatable Read 时，如果执行的是当前读，则会对读取的记录使用 Next-key Lock ，来防止其它事务在间隙间插入数据

InnoDB 对 MVCC 的实现

MVCC 的实现依赖于：隐藏字段、Read View、undo log。

在内部实现中，InnoDB 通过数据行的 DB_TRX_ID 和 Read View 来判断数据的可见性，如不可见，则通过数据行的 DB_ROLL_PTR 找到 undo log 中的历史版本。

每个事务读到的数据版本可能是不一样的，在同一个事务中，用户只能看到该事务创建 Read View 之前已经提交的修改和该事务本身做的修改

隐藏字段

在内部，InnoDB 存储引擎为每行数据添加了三个 隐藏字段：

• DB_TRX_ID（6字节）：表示最后一次插入或更新该行的事务 id。此外，delete 操作在内部被视为更新，只不过会在记录头 Record header 中的 deleted_flag 字段将其标记为已删除
• DB_ROLL_PTR（7字节） 回滚指针，指向该行的 undo log 。如果该行未被更新，则为空
• DB_ROW_ID（6字节）：如果没有设置主键且该表没有唯一非空索引时，InnoDB 会使用该 id 来生成聚簇索引

ReadView

class ReadView {
  /* ... */
private:
  trx_id_t m_low_limit_id;      /* 大于等于这个 ID 的事务均不可见 */

  trx_id_t m_up_limit_id;       /* 小于这个 ID 的事务均可见 */

  trx_id_t m_creator_trx_id;    /* 创建该 Read View 的事务ID */

  trx_id_t m_low_limit_no;      /* 事务 Number, 小于该 Number 的 Undo Logs 均可以被 Purge */

  ids_t m_ids;                  /* 创建 Read View 时的活跃事务列表 */

  m_closed;                     /* 标记 Read View 是否 close */
}

Read View 主要是用来做可见性判断，里面保存了 “当前对本事务不可见的其他活跃事务”

• m_low_limit_id：目前出现过的最大的事务 ID+1，即下一个将被分配的事务 ID。大于等于这个 ID 的数据版本均不可见
• m_up_limit_id：活跃事务列表 m_ids 中最小的事务 ID，如果 m_ids 为空，则 m_up_limit_id 为 m_low_limit_id。小于这个 ID 的数据版本均可见
• m_ids：Read View 创建时其他未提交的活跃事务 ID 列表。创建 Read View 时，将当前未提交事务 ID 记录下来，后续即使它们修改了记录行的值，对于当前事务也是不可见的。m_ids 不包括当前事务自己和已提交的事务（正在内存中）
• m_creator_trx_id：创建该 Read View 的事务 ID

undo-log

undo log 主要有两个作用：

• 当事务回滚时用于将数据恢复到修改前的样子
• 另一个作用是 MVCC ，当读取记录时，若该记录被其他事务占用或当前版本对该事务不可见，则可以通过 undo log 读取之前的版本数据，以此实现非锁定读

在 InnoDB 存储引擎中 undo log 分为两种： insert undo log 和 update undo log：

• insert undo log ：指在 insert 操作中产生的 undo log。因为 insert 操作的记录只对事务本身可见，对其他事务不可见，故该 undo log 可以在事务提交后直接删除。不需要进行 purge 操作
• update undo log ：update 或 delete 操作中产生的 undo log。该 undo log可能需要提供 MVCC 机制，因此不能在事务提交时就进行删除。提交时放入 undo log 链表，等待 purge线程 进行最后的删除

不同事务或者相同事务的对同一记录行的修改，会使该记录行的 undo log 成为一条链表，链首就是最新的记录，链尾就是最早的旧记录。

数据可见性算法

在 InnoDB 存储引擎中，创建一个新事务后，执行每个 select 语句前，都会创建一个快照（Read View），快照中保存了当前数据库系统中正处于活跃（没有 commit）的事务的 ID 号。

其实简单的说保存的是系统中当前不应该被本事务看到的其他事务 ID 列表（即 m_ids）。当用户在这个事务中要读取某个记录行的时候，InnoDB 会将该记录行的 DB_TRX_ID 与 Read View 中的一些变量及当前事务 ID 进行比较，判断是否满足可见性条件

• 如果记录 DB_TRX_ID < m_up_limit_id，那么表明最新修改该行的事务（DB_TRX_ID）在当前事务创建快照之前就提交了，所以该记录行的值对当前事务是可见的
• 如果 DB_TRX_ID >= m_low_limit_id，那么表明最新修改该行的事务（DB_TRX_ID）在当前事务创建快照之后才修改该行，所以该记录行的值对当前事务不可见。跳到步骤 5
• m_ids 为空，则表明在当前事务创建快照之前，修改该行的事务就已经提交了，所以该记录行的值对当前事务是可见的
• 如果 m_up_limit_id <= DB_TRX_ID < m_low_limit_id，表明最新修改该行的事务（DB_TRX_ID）在当前事务创建快照的时候可能处于“活动状态”或者“已提交状态”；所以就要对活跃事务列表 m_ids 进行查找（源码中是用的二分查找，因为是有序的）
  • 如果在活跃事务列表 m_ids 中能找到 DB_TRX_ID，表明：① 在当前事务创建快照前，该记录行的值被事务 ID 为 DB_TRX_ID 的事务修改了，但没有提交；或者 ② 在当前事务创建快照后，该记录行的值被事务 ID 为 DB_TRX_ID 的事务修改了。这些情况下，这个记录行的值对当前事务都是不可见的。跳到步骤 5
  • 在活跃事务列表中找不到，则表明“id 为 trx_id 的事务”在修改“该记录行的值”后，在“当前事务”创建快照前就已经提交了，所以记录行对当前事务可见
• 在该记录行的 DB_ROLL_PTR 指针所指向的 undo log 取出快照记录，用快照记录的 DB_TRX_ID 跳到步骤 1 重新开始判断，直到找到满足的快照版本或返回空

RC 和 RR 隔离级别下 MVCC 的差异

在事务隔离级别 RC 和 RR （InnoDB 存储引擎的默认事务隔离级别）下，InnoDB 存储引擎使用 MVCC（非锁定一致性读），但它们生成 Read View 的时机却不同

• 在 RC 隔离级别下的 每次 select 查询前都生成一个Read View (m_ids 列表)
• 在 RR 隔离级别下只在事务开始后 第一次 select 数据前生成一个Read View（m_ids 列表）

虽然 RC 和 RR 都通过 MVCC 来读取快照数据，但由于 生成 Read View 时机不同，从而在 RR 级别下实现可重复读

在 RC 隔离级别下，事务在每次查询开始时都会生成并设置新的 Read View，所以导致不可重复读

MVCC + Next-key-Lock 防止幻读

InnoDB存储引擎在 RR 级别下通过 MVCC和 Next-key Lock 来解决幻读问题：

执行普通 select，此时会以 MVCC 快照读的方式读取数据：

• 在快照读的情况下，RR 隔离级别只会在事务开启后的第一次查询生成 Read View ，并使用至事务提交。所以在生成 Read View 之后其它事务所做的更新、插入记录版本对当前事务并不可见，实现了可重复读和防止快照读下的 “幻读”

执行 select...for update/lock in share mode、insert、update、delete 等当前读：

• 在当前读下，读取的都是最新的数据，如果其它事务有插入新的记录，并且刚好在当前事务查询范围内，就会产生幻读！InnoDB 使用 Next-key Lock 来防止这种情况。当执行当前读时，会锁定读取到的记录的同时，锁定它们的间隙，防止其它事务在查询范围内插入数据。只要我不让你插入，就不会发生幻读

窗口函数

MySQL从8.0开始支持窗口函数，这个功能在大多商业数据库和部分开源数据库中早已支持，有的也叫分析函数。

窗口的概念非常重要，它可以理解为记录集合，窗口函数也就是在满足某种条件的记录集合上执行的特殊函数。

对于每条记录都要在此窗口内执行函数，有的函数随着记录不同，窗口大小都是固定的，这种属于静态窗口；有的函数则相反，不同的记录对应着不同的窗口，这种动态变化的窗口叫滑动窗口。

窗口函数和普通聚合函数也很容易混淆，二者区别如下：

• 聚合函数是将多条记录聚合为一条；而窗口函数是每条记录都会执行，有几条记录执行完还是几条。
• 聚合函数也可以用于窗口函数中

按照功能划分，可以把MySQL支持的窗口函数分为如下几类：

• 序号函数：row_number() / rank() / dense_rank()
• 分布函数：percent_rank() / cume_dist()
• 前后函数：lag() / lead()
• 头尾函数：first_val() / last_val()
• 其他函数：nth_value() / nfile()

窗口函数的基本用法：函数名（[expr]） over子句
其中，over是关键字，用来指定函数执行的窗口范围，如果后面括号中什么都不写，则意味着窗口包含满足where条件的所有行，窗口函数基于所有行进行计算

进阶

高可用

配置主从，即master和多个slave，slave读取主产生的bin-log日志（I/O操作）来同步数据，但是主挂了怎么办？

mycat 中间件可以做读写分离以及数据库的分片策略，但是目前还是只支持5.7以下的数据库，强制改8会出一些问题。（感觉现在差不多死了），mycat2 一直出不来

sharding-jdbc 是最近比较火的嵌入式sql代理工具，介于ORM与JDBC之间，对原有JDBC层做增强，通过拦截SQL语句，可以做读写分离与分片策略，（sharding-proxy也可以做，但是个数据库中间件，类似mycat，需要单独部署）

(目前项目中博主用的sharding-jdbc比较多)

分布式ID

在对数据库(表)水平拆分之后，表中数据的主键ID已经不能使用自增来实现了，否则会有重复，解决：

Snowflake

雪花算法（Snowflake）是twitter公司内部分布式项目采用的ID生成算法，开源后广受国内大厂的好评，在该算法影响下各大公司相继开发出各具特色的分布式生成器。

Snowflake生成的是Long类型的ID，一个Long类型占8个字节，每个字节占8比特，也就是说一个Long类型占64个比特。
Snowflake ID组成结构：正数位（占1比特）+ 时间戳（占41比特）+ 机器ID（占5比特）+ 数据中心（占5比特）+ 自增值（占12比特），总共64比特组成的一个Long类型。

• 第一个bit位（1bit）：Java中long的最高位是符号位代表正负，正数是0，负数是1，一般生成ID都为正数，所以默认为0。
• 时间戳部分（41bit）：毫秒级的时间，不建议存当前时间戳，而是用（当前时间戳 - 固定开始时间戳）的差值，可以使产生的ID从更小的值开始；41位的时间戳可以使用69年，(1L << 41) / (1000L 60 60 24 365) = 69年
• 工作机器id（10bit）：也被叫做workId，这个可以灵活配置，机房或者机器号组合都可以。
• 序列号部分（12bit），自增值支持同一毫秒内同一个节点可以生成4096个ID

//Twitter的SnowFlake算法,使用SnowFlake算法生成一个整数，然后转化为62进制变成一个短地址URL
public class SnowFlakeShortUrl {
    //起始的时间戳
    private final static long START_TIMESTAMP = 1480166465631L;
    //每一部分占用的位数
    private final static long SEQUENCE_BIT = 12;   //序列号占用的位数
    private final static long MACHINE_BIT = 5;     //机器标识占用的位数
    private final static long DATA_CENTER_BIT = 5; //数据中心占用的位数
    //每一部分的最大值
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);
    //每一部分向左的位移
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;
    private long dataCenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //序列号
    private long lastTimeStamp = -1L;  //上一次时间戳
    private long getNextMill() {
        long mill = getNewTimeStamp();
        while (mill <= lastTimeStamp) {
            mill = getNewTimeStamp();
        }
        return mill;
    }
    private long getNewTimeStamp() {
        return System.currentTimeMillis();
    }
    //根据指定的数据中心ID和机器标志ID生成指定的序列号
    //@param dataCenterId 数据中心ID
    //@param machineId    机器标志ID
    public SnowFlakeShortUrl(long dataCenterId, long machineId) {
        if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
            throw new IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0！");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("MachineId can't be greater than MAX_MACHINE_NUM or less than 0！");
        }
        this.dataCenterId = dataCenterId;
        this.machineId = machineId;
    }
    //产生下一个ID
    public synchronized long nextId() {
        long currTimeStamp = getNewTimeStamp();
        if (currTimeStamp < lastTimeStamp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }
        if (currTimeStamp == lastTimeStamp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currTimeStamp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }
        lastTimeStamp = currTimeStamp;
        return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //时间戳部分
                | dataCenterId << DATA_CENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
    }    
    public static void main(String[] args) {
        SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);

        for (int i = 0; i < (1 << 4); i++) {
            //10进制
            System.out.println(snowFlake.nextId());
        }
    }
}

基于雪花的开源分布式ID工具

uid-generator

uid-generator是由百度技术部开发。

uid-generator是基于Snowflake算法实现的，与原始的snowflake算法不同在于，uid-generator支持自定义时间戳、工作机器ID和 序列号 等各部分的位数，而且uid-generator中采用用户自定义workId的生成策略。

uid-generator需要与数据库配合使用，需要新增一个WORKER_NODE表。当应用启动时会向数据库表中去插入一条数据，插入成功后返回的自增ID就是该机器的workId数据由host，port组成。

Leaf

Leaf由美团开发。

Leaf同时支持号段模式和snowflake算法模式，可以切换使用。

Tinyid

Tinyid 由滴滴开发。

Tinyid是基于号段模式原理实现的与Leaf如出一辙，每个服务获取一个号段（1000,2000]、（2000,3000]、（3000,4000]

一致性Hash

当我们可以生成分布式ID之后的另一个重要问题就是，我们对一条记录的存放/查询策略，对于新增的数据，我们应该放在哪个数据库的哪个表？拿到一个ID，我们应该如何定位到哪个数据库的哪个表？

其中关于定位数据库的具体实现已经可以通过sharding-JDBC/proxy的配置实现了，主要是配置中的策略如何定？

由于考虑到机器扩展和宕机，对ID直接取余这种Hash操作已经不能适用，这里我们需要了解一致性Hash。

概念

一致性哈希算法也是使用取模的方法，但不是简单的对自定义数量进行取模，是对2^32取模

列式数据库

优缺

优点：

• 极高的装载速度 （最高可以等于所有硬盘IO 的总和，基本是极限了）
• 适合大量的数据而不是小数据
• 实时加载数据仅限于增加（删除和更新需要解压缩Block 然后计算然后重新压缩储存）
• 高效的压缩率，不仅节省储存空间也节省计算内存和CPU
• 非常适合做聚合操作

缺点：

• 不适合扫描小量数据
• 不适合随机的更新
• 批量更新情况各异，有的优化的比较好的列式数据库（比如Vertica）表现比较好，有些没有针对更新的数据库表现比较差
• 不适合做含有删除和更新的实时操作