mysql怎么找二叉树,mysql为什么不用二叉树

mysql如何创建二叉树

在二叉树中有一种平衡二叉树，通过平衡算法可以让二叉树两边的节点平均分布，这样就能让所有的索引查找都在一个近似的时间内完成。而MySQL这类数据库采用了二叉树的升级版B+Tree的形式，每个节点有三个支叶，不过其算法原理仍然是平衡树的原理。

创新互联专注于企业成都营销网站建设、网站重做改版、黎城网站定制设计、自适应品牌网站建设、H5建站、购物商城网站建设、集团公司官网建设、成都外贸网站建设公司、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为黎城等各大城市提供网站开发制作服务。

B+树作为Mysql索引结构的优点

面试时候经常会被问到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+ 树索引的叶子节点并不存储数据，而是存储数据的文件地址。

摘自：

mysql 为什么不用二叉树查找

两者的算法思路其实很像：比中间的小就在剩下的左边，大就在剩下的右边找 但是： 二叉树查找一般习惯是在链式存储上进行，为一个树形结构 二分查找一定在顺序存储上进行

mysql b+tree是怎么查找的

B+ 树是对 B 树的一个小升级。大部分数据库的索引都是基于 B+ 树存储的。MySQL 的 MyISAM 和 InnoDB 引擎的索引都是基于 B+ 树存储。

B+ 树最大的几个特点：

1. 非叶子节点只保留 KEY，放弃 DATA；

2. KEY 和 DATA一起，在叶子节点，并且保存为一个有序链表（正序，反序，或者双向）；

3. B+ 树的查找与 B 树不同，当某个结点的 KEY 与所查的 KEY 相等时，并不停止查找，而是沿着这个 KEY 左边的指针向下，一直查到该关键字所在的叶子结点为止。

mysql 核心内容-上

1、SQL语句执行流程

MySQL大体上可分为Server层和存储引擎层两部分。

Server层：

连接器：TCP握手后服务器来验证登陆用户身份，A用户创建连接后，管理员对A用户权限修改了也不会影响到已经创建的链接权限，必须重新登陆。

查询缓存：查询后的结果存储位置，MySQL8.0版本以后已经取消，因为查询缓存失效太频繁，得不偿失。

分析器：根据语法规则，判断你输入的这个SQL语句是否满足MySQL语法。

优化器：多种执行策略可实现目标，系统自动选择最优进行执行。

执行器：判断是否有权限，将最终任务提交到存储引擎。

存储引擎层

负责数据的存储和提取。其架构模式是插件式的，支持InnoDB、MyISAM、Memory等多个存储引擎。现在最常用的存储引擎是InnoDB，它从MySQL 5.5.5版本开始成为了默认存储引擎(经常用的也是这个)。

SQL执行顺序

2、BinLog、RedoLog、UndoLog

BinLog

BinLog是记录所有数据库表结构变更（例如create、alter table）以及表数据修改(insert、update、delete)的二进制日志，主从数据库同步用到的都是BinLog文件。BinLog日志文件有三种模式。

STATEMENT 模式

内容：binlog 记录可能引起数据变更的 sql 语句

优势：该模式下，因为没有记录实际的数据，所以日志量很少 IO 都消耗很低，性能是最优的

劣势：但有些操作并不是确定的，比如 uuid() 函数会随机产生唯一标识，当依赖 binlog 回放时，该操作生成的数据与原数据必然是不同的，此时可能造成无法预料的后果。

ROW 模式

内容：在该模式下，binlog 会记录每次操作的源数据与修改后的目标数据，StreamSets就要求该模式。

优势：可以绝对精准的还原，从而保证了数据的安全与可靠，并且复制和数据恢复过程可以是并发进行的

劣势：缺点在于 binlog 体积会非常大，同时，对于修改记录多、字段长度大的操作来说，记录时性能消耗会很严重。阅读的时候也需要特殊指令来进行读取数据。

MIXED 模式

内容：是对上述STATEMENT 跟 ROW 两种模式的混合使用。

细节：对于绝大部分操作，都是使用 STATEMENT 来进行 binlog 没有记录，只有以下操作使用 ROW 来实现：表的存储引擎为 NDB，使用了uuid() 等不确定函数，使用了 insert delay 语句，使用了临时表

主从同步流程：

1、主节点必须启用二进制日志，记录任何修改了数据库数据的事件。

2、从节点开启一个线程（I/O Thread)把自己扮演成 mysql 的客户端，通过 mysql 协议，请求主节点的二进制日志文件中的事件 。

3、主节点启动一个线程（dump Thread），检查自己二进制日志中的事件，跟对方请求的位置对比，如果不带请求位置参数，则主节点就会从第一个日志文件中的第一个事件一个一个发送给从节点。

4、从节点接收到主节点发送过来的数据把它放置到中继日志（Relay log）文件中。并记录该次请求到主节点的具体哪一个二进制日志文件内部的哪一个位置（主节点中的二进制文件会有多个）。

5、从节点启动另外一个线程（sql Thread ），把 Relay log 中的事件读取出来，并在本地再执行一次。

mysql默认的复制方式是异步的，并且复制的时候是有并行复制能力的。主库把日志发送给从库后不管了，这样会产生一个问题就是假设主库挂了，从库处理失败了，这时候从库升为主库后，日志就丢失了。由此产生两个概念。

全同步复制

主库写入binlog后强制同步日志到从库，所有的从库都执行完成后才返回给客户端，但是很显然这个方式的话性能会受到严重影响。

半同步复制

半同步复制的逻辑是这样，从库写入日志成功后返回ACK确认给主库，主库收到至少一个从库的确认就认为写操作完成。

还可以延伸到由于主从配置不一样、主库大事务、从库压力过大、网络震荡等造成主备延迟，如何避免这个问题？主备切换的时候用可靠性优先原则还是可用性优先原则？如何判断主库Crash了？互为主备的情况下如何避免主备循环复制？被删库跑路了如何正确恢复？( o )… 感觉越来越扯到DBA的活儿上去了。

RedoLog

可以先通过下面demo理解：

饭点记账可以把账单写在账本上也可以写在粉板上。有人赊账或者还账的话，一般有两种做法：

1、直接把账本翻出来，把这次赊的账加上去或者扣除掉。

2、先在粉板上记下这次的账，等打烊以后再把账本翻出来核算。

生意忙时选后者，因为前者太麻烦了。得在密密麻麻的记录中找到这个人的赊账总额信息，找到之后再拿出算盘计算，最后再将结果写回到账本上。

同样在MySQL中如果每一次的更新操作都需要写进磁盘，然后磁盘也要找到对应的那条记录，然后再更新，整个过程IO成本、查找成本都很高。而粉板和账本配合的整个过程就是MySQL用到的是Write-Ahead Logging 技术，它的关键点就是先写日志，再写磁盘。此时账本 = BinLog，粉板 = RedoLog。

1、 记录更新时，InnoDB引擎就会先把记录写到RedoLog（粉板）里面，并更新内存。同时，InnoDB引擎会在空闲时将这个操作记录更新到磁盘里面。

2、 如果更新太多RedoLog处理不了的时候，需先将RedoLog部分数据写到磁盘，然后擦除RedoLog部分数据。RedoLog类似转盘。

RedoLog有write pos 跟checkpoint

write pos ：是当前记录的位置，一边写一边后移，写到第3号文件末尾后就回到0号文件开头。

check point：是当前要擦除的位置，也是往后推移并且循环的，擦除记录前要把记录更新到数据文件。

write pos和check point之间的是粉板上还空着的部分，可以用来记录新的操作。如果write pos追上checkpoint，表示粉板满了，这时候不能再执行新的更新，得停下来先擦掉一些记录，把checkpoint推进一下。

有了redo log，InnoDB就可以保证即使数据库发生异常重启，之前提交的记录都不会丢失，这个能力称为crash-safe。 redolog两阶段提交：为了让binlog跟redolog两份日志之间的逻辑一致。提交流程大致如下：

1 prepare阶段 -- 2 写binlog -- 3 commit

当在2之前崩溃时，重启恢复后发现没有commit，回滚。备份恢复：没有binlog 。一致

当在3之前崩溃时，重启恢复发现虽没有commit，但满足prepare和binlog完整，所以重启后会自动commit。备份：有binlog. 一致

binlog跟redolog区别：

redo log是InnoDB引擎特有的；binlog是MySQL的Server层实现的，所有引擎都可以使用。

redo log是物理日志，记录的是在某个数据页上做了什么修改；binlog是逻辑日志，记录的是这个语句的原始逻辑，比如给ID=2这一行的c字段加1。

redo log是循环写的，空间固定会用完；binlog是可以追加写入的。追加写是指binlog文件写到一定大小后会切换到下一个，并不会覆盖以前的日志。

UndoLog

UndoLog 一般是逻辑日志，主要分为两种：

insert undo log

代表事务在insert新记录时产生的undo log, 只在事务回滚时需要，并且在事务提交后可以被立即丢弃

update undo log

事务在进行update或delete时产生的undo log; 不仅在事务回滚时需要，在快照读时也需要；所以不能随便删除，只有在快速读或事务回滚不涉及该日志时，对应的日志才会被purge线程统一清除

3、MySQL中的索引

索引的常见模型有哈希表、有序数组和搜索树。

哈希表：一种以KV存储数据的结构，只适合等值查询，不适合范围查询。

有序数组：只适用于静态存储引擎，涉及到插入的时候比较麻烦。可以参考Java中的ArrayList。

搜索树：按照数据结构中的二叉树来存储数据，不过此时是N叉树(B+树)。广泛应用在存储引擎层中。

B+树比B树优势在于：

B+ 树非叶子节点存储的只是索引，可以存储的更多。B+树比B树更加矮胖，IO次数更少。

B+ 树叶子节点前后管理，更加方便范围查询。同时结果都在叶子节点，查询效率稳定。

B+树中更有利于对数据扫描，可以避免B树的回溯扫描。

索引的优点：

1、唯一索引可以保证每一行数据的唯一性

2、提高查询速度

3、加速表与表的连接

4、显著的减少查询中分组和排序的时间

5、通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

索引的缺点：

1、创建跟维护都需要耗时

2、创建索引时，需要对表加锁，在锁表的同时，可能会影响到其他的数据操作

3、 索引需要磁盘的空间进行存储，磁盘占用也很快。

4、当对表中的数据进行CRUD的时，也会触发索引的维护，而维护索引需要时间，可能会降低数据操作性能

索引设计的原则不应该：

1、索引不是越多越好。索引太多，维护索引需要时间跟空间。

2、 频繁更新的数据，不宜建索引。

3、数据量小的表没必要建立索引。

应该：

1、重复率小的列建议生成索引。因为重复数据少，索引树查询更有效率，等价基数越大越好。

2、数据具有唯一性，建议生成唯一性索引。在数据库的层面，保证数据正确性

3、频繁group by、order by的列建议生成索引。可以大幅提高分组和排序效率

4、经常用于查询条件的字段建议生成索引。通过索引查询，速度更快

索引失效的场景

1、模糊搜索：左模糊或全模糊都会导致索引失效，比如'%a'和'%a%'。但是右模糊是可以利用索引的，比如'a%' 。

2、隐式类型转换：比如select * from t where name = xxx , name是字符串类型，但是没有加引号，所以是由MySQL隐式转换的，所以会让索引失效 3、当语句中带有or的时候：比如select * from t where name=‘sw’ or age=14

4、不符合联合索引的最左前缀匹配：(A,B,C)的联合索引，你只where了C或B或只有B,C

关于索引的知识点：

主键索引：主键索引的叶子节点存的是整行数据信息。在InnoDB里，主键索引也被称为聚簇索引（clustered index）。主键自增是无法保证完全自增的哦，遇到唯一键冲突、事务回滚等都可能导致不连续。

唯一索引：以唯一列生成的索引，该列不允许有重复值，但允许有空值(NULL)

普通索引跟唯一索引查询性能：InnoDB的数据是按数据页为单位来读写的，默认每页16KB，因此这两种索引查询数据性能差别微乎其微。

change buffer：普通索引用在更新过程的加速，更新的字段如果在缓存中，如果是普通索引则直接更新即可。如果是唯一索引需要将所有数据读入内存来确保不违背唯一性，所以尽量用普通索引。

非主键索引：非主键索引的叶子节点内容是主键的值。在InnoDB里，非主键索引也被称为二级索引（secondary index）

回表：先通过数据库索引扫描出数据所在的行，再通过行主键id取出索引中未提供的数据，即基于非主键索引的查询需要多扫描一棵索引树。

覆盖索引：如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为覆盖索引。

联合索引：相对单列索引，组合索引是用多个列组合构建的索引，一次性最多联合16个。

最左前缀原则：对多个字段同时建立的组合索引(有顺序，ABC，ACB是完全不同的两种联合索引) 以联合索引(a,b,c)为例，建立这样的索引相当于建立了索引a、ab、abc三个索引。另外组合索引实际还是一个索引，并非真的创建了多个索引，只是产生的效果等价于产生多个索引。

索引下推：MySQL 5.6引入了索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判断，过滤掉不符合条件的记录，减少回表字数。

索引维护：B+树为了维护索引有序性涉及到页分裂跟页合并。增删数据时需考虑页空间利用率。

自增主键：一般会建立与业务无关的自增主键，不会触发叶子节点分裂。

延迟关联：通过使用覆盖索引查询返回需要的主键，再根据主键关联原表获得需要的数据。

InnoDB存储: * .frm文件是一份定义文件，也就是定义数据库表是一张怎么样的表。*.ibd文件则是该表的索引，数据存储文件，既该表的所有索引树，所有行记录数据都存储在该文件中。

MyISAM存储：* .frm文件是一份定义文件，也就是定义数据库表是一张怎么样的表。* .MYD文件是MyISAM存储引擎表的所有行数据的文件。* .MYI文件存放的是MyISAM存储引擎表的索引相关数据的文件。MyISAM引擎下，表数据和表索引数据是分开存储的。

MyISAM查询：在MyISAM下，主键索引和辅助键索引都属于非聚簇索引。查询不管是走主键索引，还是非主键索引，在叶子结点得到的都是目的数据的地址，还需要通过该地址，才能在数据文件中找到目的数据。

PS：InnoDB支持聚簇索引，MyISAM不支持聚簇索引

4、SQL事务隔离级别

ACID的四个特性

原子性（Atomicity）：把多个操作放到一个事务中，保证这些操作要么都成功，要么都不成功

一致性（Consistency）：理解成一串对数据进行操作的程序执行下来，不会对数据产生不好的影响，比如凭空产生，或消失

隔离性（Isolation，又称独立性）：隔离性的意思就是多个事务之间互相不干扰，即使是并发事务的情况下，他们只是两个并发执行没有交集，互不影响的东西；当然实现中，也不一定需要这么完整隔离性，即不一定需要这么的互不干扰，有时候还是允许有部分干扰的。所以MySQL可以支持4种事务隔离性

持久性（Durability）：当某个操作操作完毕了，那么结果就是这样了，并且这个操作会持久化到日志记录中

PS：ACID中C与CAP定理中C的区别

ACID的C着重强调单数据库事务操作时，要保证数据的完整和正确性，数据不会凭空消失跟增加。CAP 理论中的C指的是对一个数据多个备份的读写一致性

事务操作可能会出现的数据问题

1、脏读(dirty read)：B事务更改数据还未提交，A事务已经看到并且用了。B事务如果回滚，则A事务做错了

2、 不可重复读(non-repeatable read)：不可重复读的重点是修改: 同样的条件, 你读取过的数据, 再次读取出来发现值不一样了，只需要锁住满足条件的记录

3、 幻读(phantom read)：事务A先修改了某个表的所有纪录的状态字段为已处理，未提交；事务B也在此时新增了一条未处理的记录，并提交了；事务A随后查询记录，却发现有一条记录是未处理的造成幻读现象，幻读仅专指新插入的行。幻读会造成语义上的问题跟数据一致性问题。

4、 在可重复读RR隔离级别下，普通查询是快照读，是不会看到别的事务插入的数据的。因此，幻读在当前读下才会出现。要用间隙锁解决此问题。

在说隔离级别之前，你首先要知道，你隔离得越严实，效率就会越低。因此很多时候，我们都要在二者之间寻找一个平衡点。SQL标准的事务隔离级别由低到高如下： 上图从上到下的模式会导致系统的并行性能依次降低，安全性依次提高。

读未提交：别人改数据的事务尚未提交，我在我的事务中也能读到。

读已提交(Oracle默认)：别人改数据的事务已经提交，我在我的事务中才能读到。

可重复读(MySQL默认)：别人改数据的事务已经提交，我在我的事务中也不去读，以此保证重复读一致性。

串行：我的事务尚未提交，别人就别想改数据。

标准跟实现：上面都是关于事务的标准，但是每一种数据库都有不同的实现，比如MySQL InnDB 默认为RR级别，但是不会出现幻读。因为当事务A更新了所有记录的某个字段，此时事务A会获得对这个表的表锁，因为事务A还没有提交，所以事务A获得的锁没有释放，此时事务B在该表插入新记录，会因为无法获得该表的锁，则导致插入操作被阻塞。只有事务A提交了事务后，释放了锁，事务B才能进行接下去的操作。所以可以说 MySQL的RR级别的隔离是已经实现解决了脏读，不可重复读和幻读的。

5、MySQL中的锁

无论是Java的并发编程还是数据库的并发操作都会涉及到锁，研发人员引入了悲观锁跟乐观锁这样一种锁的设计思想。

悲观锁：

优点：适合在写多读少的并发环境中使用，虽然无法维持非常高的性能，但是在乐观锁无法提更好的性能前提下，可以做到数据的安全性

缺点：加锁会增加系统开销，虽然能保证数据的安全，但数据处理吞吐量低，不适合在读书写少的场合下使用

乐观锁：

优点：在读多写少的并发场景下，可以避免数据库加锁的开销，提高DAO层的响应性能，很多情况下ORM工具都有带有乐观锁的实现，所以这些方法不一定需要我们人为的去实现。

缺点：在写多读少的并发场景下，即在写操作竞争激烈的情况下，会导致CAS多次重试，冲突频率过高，导致开销比悲观锁更高。

实现：数据库层面的乐观锁其实跟CAS思想类似， 通数据版本号或者时间戳也可以实现。

数据库并发场景主要有三种：

读-读：不存在任何问题，也不需要并发控制

读-写：有隔离性问题，可能遇到脏读，幻读，不可重复读

写-写：可能存更新丢失问题，比如第一类更新丢失，第二类更新丢失

两类更新丢失问题：

第一类更新丢失：事务A的事务回滚覆盖了事务B已提交的结果 第二类更新丢失：事务A的提交覆盖了事务B已提交的结果

为了合理贯彻落实锁的思想，MySQL中引入了杂七杂八的各种锁：

锁分类

MySQL支持三种层级的锁定，分别为

表级锁定

MySQL中锁定粒度最大的一种锁，最常使用的MYISAM与INNODB都支持表级锁定。

页级锁定

是MySQL中锁定粒度介于行级锁和表级锁中间的一种锁，表级锁速度快，但冲突多，行级冲突少，但速度慢。所以取了折衷的页级，一次锁定相邻的一组记录。

行级锁定

Mysql中锁定粒度最细的一种锁，表示只针对当前操作的行进行加锁。行级锁能大大减少数据库操作的冲突。其加锁粒度最小，但加锁的开销也最大行级锁不一定比表级锁要好：锁的粒度越细，代价越高，相比表级锁在表的头部直接加锁，行级锁还要扫描找到对应的行对其上锁，这样的代价其实是比较高的，所以表锁和行锁各有所长。

MyISAM中的锁

虽然MySQL支持表，页，行三级锁定，但MyISAM存储引擎只支持表锁。所以MyISAM的加锁相对比较开销低，但数据操作的并发性能相对就不高。但如果写操作都是尾插入，那还是可以支持一定程度的读写并发

从MyISAM所支持的锁中也可以看出，MyISAM是一个支持读读并发，但不支持通用读写并发，写写并发的数据库引擎，所以它更适合用于读多写少的应用场合，一般工程中也用的较少。

InnoDB中的锁

该模式下支持的锁实在是太多了，具体如下：

共享锁和排他锁 (Shared and Exclusive Locks)

意向锁（Intention Locks）

记录锁（Record Locks）

间隙锁（Gap Locks）

临键锁 （Next-Key Locks）

插入意向锁（Insert Intention Locks）

主键自增锁 (AUTO-INC Locks)

空间索引断言锁（Predicate Locks for Spatial Indexes）

举个栗子，比如行锁里的共享锁跟排它锁：lock in share modle 共享读锁：

为了确保自己查到的数据没有被其他的事务正在修改，也就是说确保查到的数据是最新的数据，并且不允许其他人来修改数据。但是自己不一定能够修改数据，因为有可能其他的事务也对这些数据使用了 in share mode 的方式上了S 锁。如果不及时的commit 或者rollback 也可能会造成大量的事务等待。

for update排它写锁:

为了让自己查到的数据确保是最新数据，并且查到后的数据只允许自己来修改的时候，需要用到for update。相当于一个 update 语句。在业务繁忙的情况下，如果事务没有及时的commit或者rollback 可能会造成其他事务长时间的等待，从而影响数据库的并发使用效率。

Gap Lock间隙锁：

1、行锁只能锁住行，如果在记录之间的间隙插入数据就无法解决了，因此MySQL引入了间隙锁(Gap Lock)。间隙锁是左右开区间。间隙锁之间不会冲突。

2、间隙锁和行锁合称NextKeyLock，每个NextKeyLock是前开后闭区间。

间隙锁加锁原则(学完忘那种)：

1、加锁的基本单位是 NextKeyLock，是前开后闭区间。

2、查找过程中访问到的对象才会加锁。

3、索引上的等值查询，给唯一索引加锁的时候，NextKeyLock退化为行锁。

4、索引上的等值查询，向右遍历时且最后一个值不满足等值条件的时候，NextKeyLock退化为间隙锁。

5、唯一索引上的范围查询会访问到不满足条件的第一个值为止。

MySQL——关于索引的总结

首先说说索引的 优点 ：最大的好处无疑就是提高查询效率。有的索引还能保证数据的唯一性，比如唯一索引。

而它的 坏处 也很明显：索引也是文件，我们在创建索引时，也会创建额外的文件，所以会占用一些硬盘空间。其次，索引也需要维护，我们在增加删除数据的时候，索引也需要去变化维护。当一个表的索引多了以后，资源消耗是很大的，所以必须结合实际业务再去确定给哪些列加索引。

再说说索引的基本结构。一说到这里肯定会脱口而出：B+树！了解B+树前先要了解二叉查找树和二叉平衡树。 二叉查找树 ：左节点比父节点小，右节点比父节点大，所以二叉查找树的中序遍历就是树的各个节点从小到大的排序。 二叉平衡树 ：左右子树高度差不能大于1。B+树就是结合了它们的特点，当然，不一定是二叉树。

为什么要有二叉查找树的特点？？ 因为查找效率快，二分查找在这种结构下，查找效率是很快的。 那为什么要有平衡树的特点呢？ 试想，如果不维护一颗树的平衡性，当插入一些数据后，树的形态有可能变得很极端，比如左子树一个数据没有，而全在右子树上，这种情况下，二分查找和遍历有什么区别呢？而就是因为这些特点需要去维护，所以就有了上面提到的缺点，当索引很多后，反而增加了系统的负担。

接着说B+树。 它的结构如下 ：

可以发现，叶子节点其实是一个 双向循环链表 ，这种结构的好处就是，在范围查询的时候，我只用找到一个数据，就可以直接返回剩余的数据了。比如找小于30的，只用找到30，其余的直接通过叶子节点间的指针就可以找到。再说说其他特点： 数据只存在于叶子节点 。当叶子节点满了，如果再添加数据，就会拆分叶子节点，父节点就多了个子节点。如果父节点的位置也满了，就会扩充高度，就是拆分父节点，如25 50 75拆分成：25为左子树，75为右子树，50变成新的头节点，此时B+树的高度变成了3。它们的扩充的规律如下表，Leaf Page是叶子节点，index Page是非叶子节点。

再说说B树 ，B树相比较B+树，它所有节点都存放数据，所以在查找数据时，B树有可能没到达叶子节点就结束了。再者，B树的叶子节点间不存在指针。

最后说说Hash索引 ，相较于B+树，Hash索引最大的优点就是查找数据快。但是Hash索引最大的问题就是不支持范围查询。试想，如果查询小于30的数据，hash函数是根据数据的值找到其对应的位置，谁又知道小于30的有哪几个数据。而B+树正好相反，范围查询是它的强项。

附录： Hash到底是啥？？ 哈希中文名散列，哈希只是它的音译。 为啥都说Hash快？？ 首先有一块哈希表（散列表），它的数据结构是个数组，一个任意长度的数据通过hash函数都可以变成一个固定长度的数据，叫hash值。然后通过hash值确定在数组中的位置，相同数据的hash值是相同的，所以我们存储一个数据以后，只需O(1)的时间复杂度就可以找到数据。 那hash函数又是啥？？ 算术运算或位运算，很多应用里都有hash函数，但实际运算过程大不一样。这是Java里String的hashCode方法：

publicint hashCode() {

}

还有一个问题，hash函数计算出来的hash值有可能存在碰撞，即两个不同的数据可能存在相同的hash值，在MySQL或其他的应用中，如Java的HashMap等，如果存在碰撞就会以当前数组位置为头节点，转变成一个链表。

说到这里也清楚了为啥Java中引用类型要同时重写hashCode和equals了。两个对象，实例就算一模一样，它们的hash值也不相等， 为啥不相等？？ 默认的Object的hashCode方法会根据对象来计算hash值的，实例相同，但它们还是两个不同的对象啊，所以我们重写hashCode时，最简单的方法就是调用Object的hashCode方法，然后传入该引用类型的属性，让hashCode方法只根据这几个属性来计算，那么实例相同的话，它们的hash值也会相等。等hashCode比较完后，如果相等再比较实例内容，也就是equals，确保不是hash碰撞。

索引的分类

如果我们指定了一个主键，那么这个主键就是主键索引。如果我们没有指定，Mysql就会自动找一个非空的唯一索引当主键。如果没有这种字段，Mysql就会创建一个大小为6字节的自增主键。如果有多个非空的唯一索引，那么就让第一个定义为唯一索引的字段当主键，注意，是第一个定义，而不是建表时出现在前面的。

对于辅助索引来说，它们的B+树结构稍微有点特殊，它们的叶子节点存储的是主键，而不是整个数据。所以在大部分情况下，使用辅助索引查找数据，需要二次查找。但并不是所有情况都需要二次查找。比如查找的数据正好就是当前索引字段的值，那么直接返回就行。这里提一句，B+树的key就是对应索引字段的内容。

而辅助索引又有一些分类：唯一索引：不能出现重复的值，也算一种约束。普通索引：可以重复、可以为空，一般就是查询时用到。前缀索引：只适用于字符串类型数据，对字符串前几个字符创建索引。全文索引：作用是检测大文本数据中某个关键字，这也是搜索引擎的一种技术。

注意，聚集索引、非聚集索引和前面几个索引的分类并不是一个层面上的。上面的几个分类是从索引的作用来分析的。聚集、非聚集索引是从索引文件上区分的。主键索引就属于聚集索引，即索引和数据存放在一起，叶子节点存放的就是数据。数据表的.idb文件就是存放该表的索引和数据。

辅助索引属于非聚集索引，说到这也就明白了。索引和数据不存放在一起的就是非聚集索引。在MYISAM引擎中，数据表的.MYI文件包含了表的索引， 该表的 叶子节点存储索引和索引对应数据的指针，指向.MYD文件的数据。

索引的几点使用经验

经常被查询的字段；经常作为条件查询的字段；经常用于外键连接或普通的连表查询时进行相等比较字段；不为null的字段；如果是多条件查询，最好创建联合索引，因为联合索引只有一个索引文件。

经常被更新的字段、不经常被查询的字段、存在相同功能的字段

当前文章：mysql怎么找二叉树,mysql为什么不用二叉树
网页URL：http://6mz.cn/article/hessjh.html