MySql索引 1.基础 - 首先Mysql的基本存储结构是页(记录都存在页里边)： 各个数据页可以组成一个双向链表 而每个数据页中的记录又可以组成一个单向链表 每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录 总结就是：使用二分查找算法从页目录中快速定位记录。 以其他列(非主键)作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录。 所以说，如果我们写select * from user where username = ‘Java3y’这样没有进行任何优化的sql语句，默认会这样做： 定位到记录所在的页 1.需要遍历双向链表，找到所在的页 2.从所在的页内中查找相应的记录 3.由于不是根据主键查询，只能遍历所在页的单链表了 总结就是：遍历双向链表定位页，遍历所在页的单链表定位数据。 很明显，在数据量很大的情况下这样查找会很慢！ 2.索引提高检索速度 - 一般经常需要搜索、排序、WHERE的列上加上索引，可以加快对应操作的速度。 - 索引将无序的数据变成有序(相对)： - 很明显的是：没有用索引我们是需要遍历双向链表来定位对应的页，有索引可以通过“目录”就可以很快地定位到对应的页上了！ - 其实底层结构就是B+树，B+树作为树的一种实现，能够让我们很快地查找出对应的记录。 3.索引降低增删改的速度 - B+树是平衡树的一种。 >平衡树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 如果一棵普通的树在极端的情况下，是能退化成链表的(树的优点就不复存在了) 检索的时间复杂度就是O(logn) B+树是一颗平衡树，如果我们对这颗树增删改的话，那肯定会破坏它的原有结构。 要维持平衡树，就必须做额外的工作。正因为这些额外的工作开销，导致索引会降低增删改的速度 4.聚簇和非聚簇索引 简单概括： - 聚簇索引就是以主键创建的索引，检索效率比非聚簇索引高，但对数据更新影响较大。 - 非聚簇索引就是以非主键创建的索引，非聚簇索引检索效率比聚集索引低，但对数据更新影响较小。 >非聚集索引表示数据存储在一个地方，索引存储在另一个地方，索引带有指针指向数据的存储位置。 区别： 聚簇索引在叶子节点存储的是表中的数据 非聚簇索引在叶子节点存储的是主键值 使用非聚簇索引查询出数据时，拿到叶子上的主键再去查到想要查找的数据。(拿到主键再查找这个过程叫做回表) 非聚集索引也叫做二级索引 5.索引最左匹配原则 - 索引可以简单如一个列(a)，也可以复杂如多个列(a, b, c, d)，即联合索引。 - 如果是联合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在（相等），遇到范围查询(>、<、between、like左匹配(%As))等就不能进一步匹配了，后续退化为线性查找。 - 因此，列的排列顺序决定了可命中索引的列数。 >如有索引(a, b, c, d)，查询条件a = 1 and b = 2 and c > 3 and d = 4，则会在每个节点依次命中a、b、c，无法命中d。(很简单：索引命中只能是相等的情况，不能是范围匹配) - 通过a,c条件查询能不能使用或命中这个索引？—–能 - 通过b,c条件查询能不能使用或命中这个索引？—–不能……

MySQL乐观锁电商库存并发问题应用 下单涉及的一些操作 1.下单 2.下单同时预占库存 3.支付 4.支付成功真正减扣库存 5.取消订单 6.回退预占库存 方案选择： 商品加入购物车后，选择下单，这个时候去预占库存。用户选择去支付说明了，用户购买欲望强烈的。订单也有一个时效，例如半个小时。超过半个小时后，系统自动取消订单，回退预占库存。 可进行操作： 1.UI拦截，点击后按钮置灰，不能继续点击，防止用户，连续点击造成的重复下单。 2.下单前获取一个下单的唯一token，下单的时候需要这个token。后台系统校验这个 token是否有效，才继续进行下单操作。 3.进来的时候 先 get 库存数量是否充足，再执行 increment。以 increment > 0 为准。 4.因为检查库存 与 减少库存 不是原子性的，而redis.increment 是个原子操作，可以此为准。 redisService.increment(key, -req.getNum().longValue()) >= 0 说明库存充足，可以下单。 redisService.increment(key, -req.getNum().longValue()) < 0 的时候 不能下单，次数库存不足。并且需要 回加刚刚减去的库存数量，否则会导致刚才减扣的数量 一直买不出去。数据库与缓存的库存不一致。 5.都满足进行真正的扣减库存 5.1生成订单 5.2订单超过时效，订单取消等，订单取消，库存回滚。 MySQL乐观锁电商库存并发问题应用 1.使用数据版本(Version)记录机制实现，这是乐观锁最常用的一种实现方式。 mysql> select * from t_goods; +----+--------+------+---------+ | id | status | name | version | +----+--------+------+---------+ | 1 | 1 | 道具 | 1 | | 2 | 2 | 装备 | 2 | +----+--------+------+---------+ 2 rows in set 何谓数据版本？即为数据增加一个版本标识，一般是通过为数据库表增加一个数字类型的 “version” 字段来实现。当读取数据时，将version字段的值一同读出，数据每更新一次，对此version值加一。当提交更新的时候，判断数据库表对应记录的当前版本信息与第一次取出来的version值进行比对，如果数据库表当前版本号与第一次取出来的version值相等，则予以更新，否则认为是过期数据。……

MySql锁 * 行锁 表锁 页锁 MyISAM × √ × BDB × √ √ InnoDB √ √ × 表锁：开销小，加锁快；不会出现死锁；锁定力度大，发生锁冲突概率高，并发度最低 行锁：开销大，加锁慢；会出现死锁；锁定粒度小，发生锁冲突的概率低，并发度高 页锁：开销和加锁速度介于表锁和行锁之间；会出现死锁；锁定粒度介于表锁和行锁之间，并发度一般 1.锁的分类 1.1 实现思想划分 (参考乐观锁悲观锁) - 乐观锁 - 悲观锁 1.2 从对数据操作的类型来分 读锁（S共享锁）:针对同一份数据，多个读操作可以同时进行而不会互相影响。　>SELECT * FROM table_name WHERE … LOCK IN SHARE MODE　 写锁（X排它锁）:当前写操作没有完成前，它会阻断其他写锁和读锁。 >SELECT * FROM table_name WHERE … FOR UPDATE 1.……

简述 在高并发的情况下，MySQL 事务的并发处理会带来几个问题脏读、不可重复读、幻读。由于高并发事务带来这几个问题，所以就产生了事务的隔离级别。 事务是什么 事务是数据库操作的最小工作单元，用户定义的一系列数据库操作作为一个整体一起向系统提交，要么都执行、要么都不执行。是不可分割的工作单元。 > 如果没做好并发控制，可能会造成脏读、不可重复读和幻读等问题。 可交叉程度 脏读Dirty Read（看到的数据则是不正确的） 当一个事务能看见另外一个事务未提交的数据时，就称为脏读。如果这个事务被回滚了而不是提交了，那么其它事务看到的数据则是不正确的，是“脏”的。 Non-repeatable Read(不可重复读) 两次读取到的数据不同 假设事务A读取了一行数据，接下来事务B改变了这行数据，之后事务A再一次读取这行数据，结果就是事务A两次读取到的数据不同。 Phantom Read(幻读) 发现多出来一条数据 假设事务A通过一个 where 条件读取到了一个结果集，事务B这时插入了一条符合事务A的 where 条件的数据，之后事务A通过同样的 where 条件再次查询时，发现多出来一条数据。 1.事务隔离级别(Isolation) JDBC 规范增加了隔离级别，来满足了 SQL:2003 定义的 4 种事务隔离级别。 在安装MySQL时，安装默认的隔离级别就是：可重复读。 可以通过 select @@global.tx_isolation; 来查看当前隔离级别。 隔离级别从最宽松到最严格，排序如下所示： TRANSACTION_NONE(无事务) 这意味着当前的 JDBC 驱动不支持事务，也意味着这个驱动不符合 JDBC 规范。 1.READ_UNCOMMITTED(读未提交) 允许事务看到其它事务修改了但未提交的数据，这意味着有可能是脏读、不可重复读或者、幻读。 2.READ_COMMITTED(读提交) 一个事务在未提交之前，所做的修改不会被其它事务所看见。这能避免脏读，但避免不了不可重复读和幻读。 3.**REPEATABLE_READ(可重复读取) MySQL默认的事务隔离级别 避免了脏读和不可重复读，但幻读**依然是有可能发生的。 4.SERIALIZABLE(序列化) 避免了脏读、不可重复读以及幻读。 2.Propagation事务传播行为 Propagation属性用来枚举事务的传播行为。所谓事务传播行为就是多个事务方法相互调用时，事务如何在这些方法间传播。Spring支持7种事务传播行为，默认为REQUIRED。 1.……

乐观锁和悲观锁 1.乐观锁 总是认为不会产生并发问题，每次去取数据的时候总认为不会有其他线程对数据进行修改，因此不会上锁，但是在更新时会判断其他线程在这之前有没有对数据进行修改，一般会使用版本号机制或CAS操作实现 version方式： 一般是在数据表中加上一个数据版本号version字段，表示数据被修改的次数，当数据被修改时，version值会加一。当线程A要更新数据值时，在读取数据的同时也会读取version值，在提交更新时，若刚才读取到的version值为当前数据库中的version值相等时才更新，否则重试更新操作，直到更新成功。 update table set x=x+1, version=version+1 where id=#{id} and version=#{version}; CAS操作方式： 即compare and swap 或者 compare and set，涉及到三个操作数，数据所在的内存值，预期值，新值。当需要更新时，判断当前内存值与之前取到的值是否相等，若相等，则用新值更新，若失败则重试，一般情况下是一个自旋操作，即不断的重试。 2.悲观锁 总是假设最坏的情况，每次取数据时都认为其他线程会修改，所以都会加锁（读锁、写锁、行锁等），当其他线程想要访问数据时，都需要阻塞挂起。可以依靠数据库实现，如行锁、读锁和写锁等，都是在操作之前加锁，在Java中，synchronized的思想也是悲观锁。 比如共享锁和排他锁（行锁，表锁的读写锁）都是悲观锁。 3.适用场景 悲观锁：比较适合写入操作比较频繁的场景，如果出现 大量的读取操作，每次读取的时候都会进行加锁，这样会增加大量的锁的开销，降低了系统的吞吐量。 乐观锁：比较适合读取操作比较频繁的场景，如果出现大量的写入操作，数据发生冲突的可能性就会增大，为了保证数据的一致性，应用层需要不断的重新获取数据，这样会增加大量的查询操作，降低了系统的吞吐量。 总结：两种所各有优缺点，读取频繁使用乐观锁，写入频繁使用悲观锁。 参考：https://blog.csdn.net/weixin_41835916/article/details/81487767……

Java OOM 1.什么是OOM OOM，全称“Out Of Memory”，翻译成中文就是“内存用完了”,当JVM因为没有足够的内存来为对象分配空间并且垃圾回收器也已经没有空间可回收时，就会抛出这个erro 2.为什么会OOM、出现的原因是什么? 分配的少了：比如虚拟机本身可使用的内存（一般通过启动时的VM参数指定）太少。 应用用的太多，并且用完没释放，浪费了。此时就会造成内存泄露或者内存溢出。 3.解决办法 java.lang.OutOfMemoryError: Java heap space ——>java堆内存溢出，此种情况最常见，一般由于内存泄露或者堆的大小设置不当引起。对于内存泄露，需要通过内存监控软件查找程序中的泄露代码，而堆大小可以通过虚拟机参数-Xms,-Xmx等修改。 java.lang.OutOfMemoryError: PermGen space ——>java永久代溢出，即方法区溢出了，一般出现于大量Class或者jsp页面，或者采用cglib等反射机制的情况，因为上述情况会产生大量的Class信息存储于方法区。此种情况可以通过更改方法区的大小来解决，使用类似-XX:PermSize=64m -XX:MaxPermSize=256m的形式修改。另外，过多的常量尤其是字符串也会导致方法区溢出。 java.lang.StackOverflowError ——> 不会抛OOM error，但也是比较常见的Java内存溢出。JAVA虚拟机栈溢出，一般是由于程序中存在死循环或者深度递归调用造成的，栈大小设置太小也会出现此种溢出。可以通过虚拟机参数-Xss来设置栈的大小 ps:JVM调优参数 -Xms:为jvm启动时分配的内存，比如-Xms200m，表示分配200M -Xmx:为jvm运行过程中分配的最大内存，比如-Xms500m，表示jvm进程最多只能够占用500M内存 -Xss:为jvm启动的每个线程分配的内存大小，默认JDK1.4中是256K，JDK1.5+中是1M 参考：https://blog.csdn.net/weixin_41835916/article/details/81558310……

Java内存模型 1.java程序执行过程: >Java源代码文件(.java后缀)会被Java编译器编译为字节码文件(.class后缀)，然后由JVM中的类加载器加载各个类的字节码文件，加载完毕之后，交由JVM执行引擎执行。在整个程序执行过程中，JVM会用一段空间来存储程序执行期间需要用到的数据和相关信息，这段空间一般被称作为Runtime Data Area（运行时数据区），也就是我们常说的JVM内存。因此，在Java中我们常常说到的内存管理就是针对这段空间进行管理（如何分配和回收内存空间）。 2.运行时数据区包括哪几部分： 2.1 方法区（Method Area） 方法区是各个线程共享的内存区域，它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。当方法区无法满足内存分配需求时，将抛出OutOfMemoryError 异常。 方法区里存放着类的版本，字段，方法，接口和常量池。常量池里存储着字面量和符号引用。符号引用包括： 1.类的全限定名 2.字段名和属性 3.方法名和属性。 2.2 JVM堆（Java Heap） Java 堆也是属于线程共享的内存区域，它在虚拟机启动时创建，是Java 虚拟机所管理的内存中最大的一块，主要用于存放对象实例，几乎所有的对象实例都在这里分配内存，注意Java 堆是垃圾收集器管理的主要区域，因此很多时候也被称做GC堆，如果在堆中没有内存完成实例分配，并且堆也无法再扩展时，将会抛出OutOfMemoryError 异常。 2.3 程序计数器(Program Counter Register)： 字节码解释器工作时，通过改变这个计数器的值来选取下一条需要执行的字节码指令，分支、循环、跳转、异常处理、线程恢复等基础功能都需要依赖这个计数器来完成。 多线程中，为了让线程切换后能恢复到正确的执行 位置，每条线程都需要有一个独立的程序计数器，各条线程之间互不影响、独立存储，因此这块内存是线程私有的。 2.4 虚拟机栈(Java Virtual Machine Stacks)： Java虚拟机栈也是线程私有的，它的生命周期与线程相同。虚拟机栈描述的是Java方法执行的内存模型：每个方法在执行的同时都会创建一个栈帧用于存储局部变量表、操作数栈、动态链表、方法出口信息等。每一个方法从调用直至执行完成的过程，就对应着一个栈帧在虚拟机栈中入栈到出栈的过程。 2.5 本地方法栈(Native Method Stacks)： 本地方法栈属于线程私有的数据区域，这部分主要与虚拟机用到的 Native 方法相关，一般情况下，我们无需关心此区域。 参考：http://blog.csdn.net/javazejian/article/details/72772461……

1.什么是布隆过滤器？ 一个名叫 Bloom 的人提出了一种来检索元素是否在给定大集合中的数据结构，这种数据结构是高效且性能很好的，但缺点是具有一定的错误识别率和删除难度。并且，理论情况下，添加到集合中的元素越多，误报的可能性就越大。 >位数组中的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1。这样申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000⁄1024 kb ≈ 122kb 的空间。 > bit数组 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2.布隆过滤器的原理 当一个元素加入布隆过滤器中的时候，会进行如下操作： 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。 根据得到的哈希值，在位数组中把对应下标的值置为 1。 当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作： 对给定元素再次进行相同的哈希计算； 得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。 布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。 3.使用Google开源的 Guava中自带的布隆过滤器 创建了一个最多存放 最多 1500个整数的布隆过滤器，并且我们可以容忍误判的概率为百分之（0.……

缓存 1.基本思想 避免用户在请求数据的时候获取速度过于缓慢，所以我们在数据库之上增加了缓存这一层来弥补。 2.本地缓存解决方案 常见的有Ehcache、guavaCache、Caffeine Cache等，性能最优的为Caffeine cache。 常见的单体架构使用 Nginx 来做负载均衡，部署两个相同的服务到服务器，两个服务使用同一个数据库，并且使用的是本地缓存。 3.为什么要用分布式缓存？而不用本地缓存？ 本地缓存存在局限性： 本地缓存对分布式架构支持不友好，比如同一个相同的服务部署在多台机器上的时候，各个服务之间的缓存是无法共享的，因为本地缓存只在当前机器上有。 本地缓存容量受服务部署所在的机器限制明显。 如果当前系统服务所耗费的内存多，那么本地缓存可用的容量就很少。 4.缓存读写模式/更新策略/处理流程 Cache Aside Pattern（旁路缓存模式） 读：从 cache 中读取数据，读取到就直接返回 。读取不到的话，先从 DB 加载，写入到 cache 后返回响应。 写：更新 DB，然后直接删除 cache 。 Read/Write Through Pattern（读写穿透） 读：从 cache 中读取数据，读取到就直接返回 。读取不到的话，先从 DB 加载，写入到 cache 后返回响应。 写：先查 cache，cache 中不存在，直接更新 DB。 cache 中存在，则先更新 cache，然后 cache 服务自己更新 DB（同步更新 cache 和 DB）。 Write Behind Pattern（异步缓存写入） 读：从 cache 中读取数据，读取到就直接返回 。读取不到的话，先从 DB 加载，写入到 cache 后返回响应。 写：无论是否存在，都直接跟新缓存，最好异步批量的方式来更新 DB。 ……

小灰的算法之旅 1.算法和数据结构 算法是什么？ 算法是一系列程序指令，用来处理特定运算和逻辑问题。 什么是数据结构？ 数据结构是数据的组织、管理和存储格式，其使用的目的是为了高效的访问和修改。 数据结构包含数组，链表。以及树，图这种复杂的数据结构。 3.什么是时间复杂度？ T(n) = O(f(n)) 4.什么是空间复杂度？ S(n) = O(f(n)) 2.数据结构基础 数组VS链表 VS 查找 更新 插入 删除 数组 O(1) O(1) O(n) O(n) 链表 O(n) O(1) O(1) O(1) 栈和队列 栈是先入后出FILO(First In Last Out) 入栈：PUSH 出栈：POP 可以用来实现递归逻辑，以及面包屑导航（浏览器浏览历史回退） 队列是先入先出FIFO(First In First Out) 队头:Front 队尾：Rear 入队：enquere 出队：dequeue 散列表（哈希表 hash table） 散列表也叫哈希表，是存储Key-Value的集合，对于一个key，散列表可以在接近 O(1)的时间内完成读写操作。散列表通过哈希函数实现key和数组下标的转换，通过开放寻址法和链表法来解决冲突。 哈希函数：通过哈希函数，可以将字符串和其他类型的Key，转换成数组下标index 例如Key=abcd,index= HashCode(“abcd”)%Array.……