数据库之通关Mysql不要太难（一）
宝剑锋从磨砺出，梅花香自苦寒来,大家好，我是 小码哥
今天把pdf中的《MYSQL》的基础面试题整理出来了，这是第一篇《第二篇链接地址》希望看完对大家面试有所收获！
1、说一说数据库的三大范式
第一范式: 每个列都不可以再拆分。
第二范式: 非主键列完全依赖于主键,而不能是依赖于主键的一部分. 。
第 三范式: 非主键列只依赖于主键,不依赖于其他非主键.。
在设计数据库结构的时候,要尽量遵守三范式,如果不遵守,必须有足够的理由.比如性能. 事实上我们经常会 为了性能而妥协数据库的设计。.
2、Mysql有哪些部分组成以及作用
1、server
-
连接器: 管理连接, 权限验证.
-
分析器: 词法分析, 语法分析.
-
优化器: 执行计划生成, 索引的选择.
-
执行器: 操作存储引擎, 返回执行结果.
2、储存引擎
-
存储数据, 提供读写接口.
3、字段为什么要求定义成not null
MySQL官网这样介绍:
NULL columns require additional space in the rowto record whether their values are NULL. For MyISAM tables, each NULL columntakes one bit extra, rounded up to the nearest byte. null值会占用更多的字节,且会在程序中造成很多与预期不符的情况.
4、ACID是什么？可以详细说一下嘛
A=Atomicity
原子性就是上面说的,要么全部成功,要么全部失败.不可能只执行一部分操作。
C=Consistency
一致性系统(数据库)总是从一个一致性的状态转移到另一个一致性的状态,不会存在中间状态.
I=Isolation
隔离性通常来说:一个事务在完全提交之前,对其他事务是不可见的.注意前面的通常来说加了红色,意味着 有例外情况.
D=Durability
持久性一旦事务提交,那么就永远是这样子了,哪怕系统崩溃也不会影响到这个事务的结果.
5、同时有多个事务正在进行提交，会怎么样呢？
事务（transaction）是作为一个单元的一组有序的数据库操作。如果组中的所有操作都成功， 则认为 事务成功， 即使只有一个操作失败， 事务也不成功。如果所有操作完成， 事务则提交， 其修改将作用 于所有其他数据库进程。如果一个操作失败， 则事务将回滚， 该事务所有操作的影响都将取消。
事务特性
-
原子性即不可分割性， 事务要么全部被执行， 要么就全部不被执行。
-
一致性或可串性事务的执行使得数据库从一种正确状态转换成另一种正确状 态
-
隔离性在事务正确提交之前，不允许把该事务对数据的任何改变提供给任何 其他事务，
-
持久性事务正确提交后， 其结果将永久保存在数据库中， 即使在事务提交后有了其他故障， 事务 的处理结果也会得到保存。或者这样理解：事务就是被绑定在一起作为一个逻辑工作单元的 SQL 语句分 组， 如果任何一个语句操作失败那么整个操作就被失败， 以后操作就会回滚到操作前状态， 或者是上 有个节点。为了确保要么执行， 要么不执行， 就可以使用事务。要将有组语句作为事务考虑， 就需要 通过 ACID 测试， 即原子性， 一致性， 隔离性和持久性。
6、Mysql索引分哪些？
从数据结构角度
1、B+树索引(O(log(n)))：关于B+树索引，
2、hash索引： a 仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询 b 其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引 c 只有Memory存储引擎显示支持hash索引
3、FULLTEXT索引（现在MyISAM和InnoDB引擎都支持了）
4、R-Tree索引（用于对GIS数据类型创建SPATIAL索引）
从物理存储角度
1、聚集索引（clustered index）
2、非聚集索引（non-clustered index）
聚集索引和非聚集索引的区别如下：
-
聚集索引和非聚集索引的根本区别是表记录的排列顺序和与索引的排列顺序是否一致，聚集索引表记录的排列顺序与索引的排列顺序一致，优点是查询速度快，因为一旦 具有第一个索引值的纪录被找到，具有连续索引值的记录也一定物理的紧跟其后。
-
聚集索引的缺点是对表进行修改速度较慢，这是为了保持表中的记录的物理顺序与索 引的顺序一致，而把记录插入到数据页的相应位置，必须在数据页中进行数据重排， 降低了执行速度。非聚集索引指定了表中记录的逻辑顺序，但记录的物理顺序和索引的顺序不一致，聚集索引和非聚集索引都采用了B+树的结构，但非聚集索引的叶子层并不与实际的
-
从逻辑角度
1、主键索引：主键索引是一种特殊的唯一索引，不允许有空值
2、普通索引或者单列索引
3、多列索引（复合索引）：复合索引指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。使用复合索引时遵循最左前缀集合
4、唯一索引或者非唯一索引
5、空间索引：空间索引是对空间数据类型的字段建立的索引，MYSQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING、POLYGON。MYSQL使用SPATIAL关键字进行扩展，使得能够用于创建正规索引类型的语法创建空间索引。创建空间索引的列，必须将其声明为NOT NULL，空间索引只能在存储引擎为MYISAM的表中创建
CREATE TABLE table_name[col_name data type] [unique|fulltext|spatial][index|key][index_name](col_name[length])[asc|desc]
1、unique|fulltext|spatial为可选参数，分别表示唯一索引、全文索引和空间索引；
2、index和key为同义词，两者作用相同，用来指定创建索引
3、col_name为需要创建索引的字段列，该列必须从数据表中该定义的多个列中选择；
4、index_name指定索引的名称，为可选参数，如果不指定，MYSQL默认col_name为索引值；
5、length为可选参数，表示索引的长度，只有字符串类型的字段才能指定索引长度；
6、asc或desc指定升序或降序的索引值存储
7、建立了主键索引还可以建立唯一索引吗？
一、主键与索引的区别如下：
-
主键是一种约束，唯一索引是一种索引，两者在本质上是不同的。
-
主键创建后一定包含一个唯一性索引，唯一性索引并不一定就是主键。
-
唯一性索引列允许空值，而主键列不允许为空值。
-
主键列在创建时，已经默认不为空值 + 唯一索引了。
-
主键可以被其他表引用为外键，而唯一索引不能。
-
一个表最多只能创建一个主键，但可以创建多个唯一索引。
-
主键更适合那些不容易更改的唯一标识，如自动递增列、身份证号等。
二、回答
主键是一种约束，目的是对这个表的某一列进行限制； 唯一索引是一种索引，索引是数据库表的一个冗余结构，目的是为了更好的查询； 主键列不允许为空值，而唯一性索引列允许空值； 一个表最多只能一个主键，但是可以包含多个唯一索引；
1、一个表中可以有多个唯一索引，但是只能有一个主键。
2、主键一定是唯一性索引，唯一性索引并不一定就是主键
主键不允许为空，唯一键允许为空，空值不受唯一约束，也就是说可以有多个空值。
注：可以多列组合成一个唯一索引或者一个主键，即组合索引或组合主键
8、建立索引常用的知识和规则如下：
1、表的主键、外键必须有索引； 2、数据量超过300的表应该有索引； 3、经常与其他表进行连接的表，在连接字段上应该建立索引； 4、经常出现在Where子句中的字段，特别是大表的字段，应该建立索引； 5、索引应该建在选择性高的字段上； 6、索引应该建在小字段上，对于大的文本字段甚至超长字段，不要建索引； 7、复合索引的建立需要进行仔细分析；尽量考虑用单字段索引代替： 8、频繁进行数据操作的表，不要建立太多的索引； 9、删除无用的索引，避免对执行计划造成负面影响；
9、聚合索引和非聚合索引的区别
一、聚集索引 定义：数据行的物理顺序与列值（一般是主键的那一列）的 逻辑顺序相同，一个表中只能拥有一个聚集索引。
注： 1、由于物理排列方式与聚集索引的顺序相同，所以也就只能建立一个聚集索引了。
2、从下图可以看出聚集索引的好处了，索引的 叶子节点就是对应的数据节点，可以直接获取到对应的全部列的数据，而非聚集索引在索引没有覆盖到对应的列的时候需要进行二次查询，后面会详细讲。因此在查询方面聚集索引的速度往往会更占优势。
3、如果不创建索引，系统会自动创建一个隐含列作为表的聚集索引。
4、SQL Sever默认主键为聚集索引，也可以指定为非聚集索引，而MySQL里主键就是聚集索引
二、非聚集索引 定义：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。
1、其实按照定义，除了聚集索引以外的索引都是非聚集索引，只是人们想细分一下非聚集索引，分成普通索引，唯一索引，全文索引。如果非要把非聚集索引类比成现实生活中的东西，那么非聚集索引就像新华字典的偏旁字典，他结构顺序与实际存放顺序不一定一致。
2、非聚集索引叶节点仍然是索引节点，只是有一个指针指向对应的数据块，此如果使用非聚集索引查询，而查询列中包含了其他该索引没有覆盖的列，那么他还要进行第二次的查询，查询节点上对应的数据行的数据。
3、使用以下语句进行查询，不需要进行二次查询，直接就可以从非聚集索引的节点里面就可以获取到查询列的数据。
select id, username from t1 where username = '小明' select username from t1 where username = '小明'
4、但是使用以下语句进行查询，就需要二次的查询去获取原数据行的score：
select username, score from t1 where username = '小明' 5、可以看的出二次查询所花费的查询开销占比很大，达到50%。 6、聚集索引与非聚集索引区别原理图如下：
三、根本区别 1、区别：数据行的物理顺序与表的某个列值的逻辑顺序是否一致。
2、使用示例证明：
create database IndexDemo go use IndexDemo go create table ABC ( A int not null, B char(10), C varchar(10) ) go insert into ABC select 1,'B','C' union select 5,'B','C' union select 7,'B','C' union select 9,'B','C' go select * from abc
第二步：插入一条数据
insert into abc values('6','B','C') 
第三步：创建聚集索引（注意：排列变成有序）
create clustered index CLU_ABC on abc(A) 
第四步：删除聚集索引（注意：排列变成无序）
drop index abc.CLU_ABC 第五步：非聚集索引，添加新的记录，查看表顺序，如图四，并没有影响表的顺序
create nonclustered index NONCLU_ABC on abc(A) insert into abc values('4','B','C')
10、为什需要对数据加索引，为什么需要索引
当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。
1、索引是数据库本身在执行的时候调用的，而不是我们去程序中使用
2、在常常需要进行查询的才需要建立索引，需要提高查询效率的时候
3、并不是建立索引了就一定会提高数据库的查询效率，在查询数据超过30%的情况就完全没必要使用了
然后索引怎么去使用？
在查询sql中where条件中使用索引列
怎么查看索引被调用了?
执行计划中可以体现用到了的索引有那些，在Navicat for sql中查询执行计划是点‘解释’查看possible_keys列用到的索引，pl/sql可以直接查看
那建立索引的作用以及优缺点？
作用：
-
快速查询数据
-
保证数据的唯一性
-
实现表与表之间的参照完整性
-
在使用order by、group by子句进行数据检索时，利用索引可以减少排序和分组的时间。
优点：
1、加快查询速度，提高系统的性能，这也是创建索引的最主要的原因。
2.、通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
3、加速表之间的连接
4、减少查询中分组和排序的时间
缺点：
创建索引和维护索引要耗费时间，这种时间随着数据 量的增加而增加。 索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
11、数据库中的数据结构
阵列
-
二维阵列是最简单的数据结构。一个表可以看做是一个阵列：
这个二维阵列是带有行与列的表：
-
每个行代表一个主体
-
列用来描述主体的特征
-
每个列保存某一种类型对数据
当要查找特定的值时，这种数据结构需要对每一行的值进行判断。这会造成N次运算，复杂度是O(N)
树和数据库索引
-
二叉查找树/二叉搜索树：
一种带有特殊属性的二叉树，每个节点的值满足：
-
比保存在左子树的任何键值都要大
-
比保存在右子树的任何键值都要小
-
这个树有N=15个元素。如果要找208，会从根节点开始寻找：
-
136 < 208 --> 去找节点136的右子树
-
398 > 208 --> 去找节点398的左子树
-
250>208 --> 去找节点250的左子树
-
200<208 --> 去找节点200的右子树。但是 200 没有右子树，值不存在（因为如果存在，它会在 200 的右子树）
一次查询的成本基本就是树内部的层数，这个成本是log(N)
B+树索引
查找一个特定的值时，二叉查找树挺好用的，但是当我们需要查找某一个范围之间的多个元素时，我们还是要对每一个节点进行遍历，以判断它是否处于那两个值之间,这样你必须读取整个树，成本是O(N)。 为了解决这个问题，现代数据库使用了一种修订版的树---B+树:
-
只有最底层的叶子节点才保存信息
-
其它节点只是用来指引到正确的节点
可以看到节点多了两倍，同时最底层的节点是跟后续节点相连的。
用这个B+树，如果要找某个范围内(例如40到100之间)的值：
-
找到40（49不存在则找40之后最贴近的值），就像在二叉查找树中的那样。
-
向后遍历节点，直到找到100
找到了 M 个后续节点，树总共有 N 个节点。对指定节点的搜索成本是 log(N)，跟上一个树相同。但是当你找到这个节点之后，你可以通过后续节点的连接得到 M 个后续节点，这需要 M 次运算。那么这次搜索只消耗了 M+log(N) 次运算
这种方式方便查找，但是需要在节点之间保持顺序，所以在插入和删除数据时，为了维护这个B+树，需要以每个索引O(log(N))的代价来更新索引。这样的话就会减慢插入/更新/删除的操作。
哈希表
这个数据结构被数据库用来保存一些内部的东西（比如锁表或者缓冲池） 哈希表可以通过关键字来快速找到一个元素，为了构建一个hash表，你需要定义：
-
元素的关键字
-
哈希函数： 根据元素的关键字给出对应的hash值
-
比较函数：通过hash值在桶中找到需要的元素
例子：
对于这个存储数字的hash表，我们定义：
-
元素关键字： 数字本身
-
哈希函数： 对10取模
def hash(num): return num % 10
-
比价函数：判断两个整数是否相等
寻找元素78：
-
hash(78) = 8
-
查找hash桶8，找到第一个元素78,
-
返回78
搜索耗费了2次运算
找元素 59：
-
哈希表计算 59 的哈希码，等于9。
-
查找哈希桶 9，第一个找到的元素是 99。因为 99 不等于 59， 那么 99 不是正确的元素。
-
用同样的逻辑，查找第二个元素(9)，第三个(79)，……，最后一个(29)。 元素不存在。
搜索耗费了 7 次运算。
从列子可以看出，根据查找的值，每次寻找的成本(计算次数)可能并不相同。
一个好的hash函数会将所有的元素尽可能地均匀分配在hash桶中，这样会尽可能地减少查找次数。
如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1)。
阵列 vs 哈希表
-
一个哈希表可以只装载一半到内存，剩下的哈希桶可以留在硬盘上。
-
用阵列的话，你需要一个连续内存空间。如果你加载一个大表，很难分配足够的连续内存空间。
-
用哈希表的话，你可以选择你要的关键字（比如，一个人的国家和姓氏）。
12、最左前缀优化原则
在生成索引时，如果是联合索引，则将会根据联合索引声明的顺序组织B+树的非叶节点，所以在使用Select在索引上查询时，会根据联合索引的顺序对每层节点进行排序，这才需要在使用Select语句时，注意是否使用了索引。
13、二叉树
-
二叉查找树（BST）： 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； （4）没有键值相等的节点（因此，插入的时候一定是叶子节点）。
-
插入有序节点，退化成单支树 1.查找效率最好O(logn)，最坏O(n) 2.插入效率和查找效率相同（只插入叶子节点） 3.删除效率最好O(logn)+O(1)->只有左子树或者右子树 最差O(logn)+O(logn)->左子树和右子树同时存在
插入删除算法
插入算法
首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。
删除算法
若p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。 若p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点f的左子树（当p是左子树）或右子树（当p是右子树）即可，作此修改也不破坏二叉排序树的特性。 若p结点的左子树和右子树均不空。在删去p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法： 其一是令p的左子树为f的左/右(依p是f的左子树还是右子树而定)子树，s为p左子树的最右下的结点，而p的右子树为s的右子树； 其二是令p的直接前驱（或直接后继）替代p，然后再从二叉排序树中删去它的直接前驱（或直接后继）－即让f的左子树(如果有的话)成为p左子树的最左下结点(如果有的话)，再让f成为*p的左右结点的父结点。 在二叉排序树上删除一个结点的算法如下：
package 二叉查找树;
public class main{
private static class BinnarySearchTree {
private class Node {
private Node left = null;
private Node right = null;
private Node parent = null;
private Integer value = null;
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node(Node left, Node right, Node parent, Integer value) {
super();
this.left = left;
this.right = right;
this.parent = parent;
this.value = value;
}
}
private Node root = null;
public void insert(Integer value) throws Exception {
insertNode(new Node(null, null, null, value));
}
private void insertNode(Node node) throws Exception {
Node pre = null;
Node x = this.root;
while (x != null) {
pre = x;
if (x.getValue() > node.getValue()) {
x = x.getLeft();
} else if (x.getValue() < node.getValue()) {
x = x.getRight();
} else {
throw new Exception("value is existed");
}
}
if (pre != null) {
if (node.getValue() < pre.getValue()) {
pre.setLeft(node);
} else {
pre.setRight(node);
}
node.setParent(pre);
} else {
// 根节点
this.root = node;
}
}
public Node find(Integer value) {
Node x = root;
while (x != null && x.getValue() != value) {
if (x.getValue() > value) {
x = x.getLeft();
} else if (x.getValue() < value) {
x = x.getRight();
}
}
return x;
}
public void delete(Integer value) throws Exception {
Node x = find(value);
if (x != null) {
if (x.getLeft() == null && x.getRight() == null) {
// 叶子节点
x.setLeft(null);
x.setRight(null);
} else if (x.getLeft() != null) {
// 左子树不为空
Node y = x.getLeft();
while (y.getRight() != null) {
y = y.getRight();
}
x.setValue(y.getValue());
System.out.println(y.getParent());
y.getParent().setRight(null);
} else {
// 右子树不为空
Node y = x.getRight();
if (x.getParent() != null) {
y.setLeft(x.getLeft());
if (x.getParent().getValue() > x.getValue()) {
x.getParent().setLeft(y);
} else {
x.getParent().setRight(y);
}
} else {
// 根节点
this.root = y;
}
}
} else {
throw new Exception("value is not exists");
}
}
public void inOrder(Node node) {
if (node != null && node.getValue() != null) {
inOrder(node.getLeft());
System.out.println(node.getValue());
inOrder(node.getRight());
}
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
}
public static void main(String[] args) throws Exception {
BinnarySearchTree bt = new BinnarySearchTree();
bt.insert(7);
bt.insert(11);
bt.insert(8);
bt.insert(12);
bt.insert(9);
bt.insert(13);
bt.insert(10);
bt.inOrder(bt.getRoot());
System.out.println("----------------------");
bt.delete(11);
bt.inOrder(bt.getRoot());
}
}
平衡二叉查找树
平衡二叉搜索树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。
调整平衡的基本思想： 当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。 所谓最小不平衡子树，指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
先插入指定节点，记录下当前节点的信息，LH，EH或者RH。
-
若左子树高LH，查看其左子树根节点的信息，若是LH，则一次右旋；若是RH，则一次左旋+一次右旋
-
若右子树高RH，查看右子树根节点的信息，若是RH，则一次左旋；若是LH，则一次右旋+一次左旋
-
调整改变的节点信息
追求绝对的高度平衡，随着树的高度的增加，动态插入和删除的代价也随之增加。
14、红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 二叉平衡树的严格平衡策略以牺牲建立查找结构(插入，删除操作)的代价，换来了稳定的O(logN) 的查找时间复杂度 它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
(1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！] (4) 如果一个节点是红色的，则它的子节点必须是黑色的。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
RBT 的操作代价分析：
(1) 查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。 (2) 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。 (3) 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。 RBT 效率总结 : 查找 效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。 插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。
红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。
插入操作：
1.插入根节点（不需要操作） 2.父节点为黑色(不需要操作) 3.父节点和兄弟节点为红色，祖父节点为黑色，只需要变色，将祖父节点递归检查（原本检查自己） 4.父节点为红色，兄弟节点为黑色，祖父节点为红色，先两次旋转再调整颜色（左旋+右旋）
删除操作：
1.删除只有一个新的根节点（直接删除） 2.父节点为黑色，兄弟节点为红色（先旋转成左左，再删除） 3.父节点为黑色，兄弟节点为黑色（先将兄弟节点换成红色，变成情况2） 4.父节点为红色，自己和兄弟节点为黑色（将父节点变成黑色，兄弟节点变成红色，变成情况2） 5.兄弟节点为黑色，兄弟节点左子树根节点为红色（交换颜色，旋转成为左左） 6.情况2和情况5，调整性质5（将N删掉，用子节点顶替，若子节点为红色，则重绘为黑色）
15、B树（多叉查找树）：
B-树
m阶B-树
-
树中每个结点至多有m个孩子；
-
除根结点和叶子结点外，其它每个结点至少有[m/2]个孩子；
-
若根结点不是叶子结点，则至少有2个孩子；
-
所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
-
每个非终端结点中包含有n个关键字信息： (n，A0，K1，A1，K2，A2，……，Kn，An)。其中， a) Ki (i=1…n)为关键字，且关键字按顺序排序Ki < K(i-1)。 b) Ai为指向子树根的接点，且指针A(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。 c) 关键字的个数n必须满足： [m/2]-1 <= n <= m-1 建立 由于B~树结点中的关键字个数必须>=[m/2]-1。因此和平衡二叉树不同，每一次插入一个关键字并不是在树中添加一个结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成。否则，要产生结点的”分裂” 。 外存 我们现在把整棵树构造在磁盘中，假如每个盘块可以正好存放一个B~树的结点（正好存放2个文件名）。那么一个BTNode结点就代表一个盘块，而子树指针就是存放另外一个盘块 （详细见《外部存储器—磁盘 》）的地址。 现在我们模拟查找文件29的过程： (1) 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作1次】 (2) 此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。 (3) 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作2次】 (4) 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。 (5) 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作3次】 (6) 此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。
分析一下上面的过程，我们发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于3次磁盘IO操作时影响整个B~树查找效率的决定因素。
当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘IO操作最少4次，最多5次。而且文件越多，B~树比平衡二叉树所用的磁盘IO操作次数将越少，效率也越高。 B+树
B+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一颗B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。 B+ 树通常用于数据库和操作系统的文件系统中。 NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。 B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。 B+ 树元素自底向上插入。
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B 树的叶子节点并没有包括全部需要查找的信息) 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(而B 树的非终节点也包含需要查找的有效信息)
1) 有n棵子树的结点中含有n个关键字； (B~树是n棵子树有n+1个关键字) 2) 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (B~树的叶子节点并没有包括全部需要查找的信息) 3) 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (B~树的非终节点也包含需要查找的有效信息) B+树的有效内容均在叶子节点， B-树的有效内容不全在叶子节点上 B+树的头指针有两个，一个指向根节点，另一个指向关键字最小的元素，因此B+树有两种遍历的方式： 1.从根节点开始随机查询 2.从最小关键词顺序查询
B*树
为什么说B+树比B*树更适合实际应用中操作系统的文件索引和数据库索引？ B+树的磁盘读写代价更低 B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B *树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。 举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B *树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
B+树的查询效率更加稳定 由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
16、B+树和B-树的区别
B+树性质：
B+树是B-树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了： 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）； 4.为所有叶子结点增加一个链指针； 5.所有关键字都在叶子结点出现；
B-树性质：
是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2； 2.根结点的儿子数为[2, M]； 3.除根结点以外的非叶子结点的儿子数为[M/2, M]； 4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字） 5.非叶子结点的关键字个数=指向儿子的指针个数-1； 6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]； 7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树； 8.所有叶子结点位于同一层；
17、红黑树和平衡二叉树区别如下：
1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。 2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。
18、二叉树、红黑树、B树小结
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；
19、Undo原理：（备份旧数据）
在操作任何数据之前，首先将数据备份到一个地方（这个存储数据备份的地方称为Undo Log）。然后进行数据的修改。如果出现了错误或者用户执行了ROLLBACK语句，系统可以利用Undo Log中的备份将数据恢复到事务开始之前的状态。
20、Redo原理：（保存最新数据）
和Undo Log相反，Redo Log记录的是新数据的备份。在事务提交前，只要将Redo Log持久化即可，不需要将数据持久化。当系统崩溃时，虽然数据没有持久化，但是Redo Log已经持久化。系统可以根据Redo Log的内容，将所有数据恢复到最新的状态。
21、MySQL的并发控制与加锁分析
MVCC的设计目的是什么，怎么使用版本号判断数据的可见性
MVCC是一种多版本并发控制机制。锁机制可以控制并发操作,但是其系统开销较大,而MVCC可以在大多数情况下代替行级锁,使用MVCC,能降低其系统开销。 1、人们一般把基于锁的并发控制机制称成为悲观机制，而把MVCC机制称为乐观机制。这是因为锁机制是一种预防性的，读会阻塞写，写也会阻塞读，当锁定粒度较大，时间较长时并发性能就不会太好；而MVCC是一种后验性的，读不阻塞写，写也不阻塞读，等到提交的时候才检验是否有冲突，由于没有锁，所以读写不会相互阻塞，从而大大提升了并发性能。 2、MVCC的一种简单实现是基于CAS（Compare-and-swap）思想的有条件更新（Conditional Update）。普通的update参数只包含了一个keyValueSet’，Conditional Update在此基础上加上了一组更新条件conditionSet { … data[keyx]=valuex, … }，即只有在D满足更新条件的情况下才将数据更新为keyValueSet’；否则，返回错误信息。
22、SQL中定义的四种标准隔离级别
在SQL标准中定义了四种隔离级别，每一种级别都规定了一个事务中所做的修改，哪些是在事务内和事务间可见 的，哪些是不可见的。较低级别的隔离通常可以执行更高的并发，系统的开销也更低。
-
未提交读（Read uncommitted）：在未提交读级别，事务中的修改，即使没有提交，对其他事务也都是可见的。事务可以读取未提交的数据，这也被称为脏读（Dirty Read）。这个级别会导致很多问题，从性能上来说，未提交读不会比其他的级别好太多，但是缺乏其他级别的很多好处，在实际应用中一般很少使用。
-
提交读（Read committed）：大多数数据库系统的默认隔离级别都是提交读（但Mysql不是）。提交读满足前面提到的隔离性的简单定义：一个事务开始时，只能“看见”已经提交的事务所做的修改。换句话说，一个事务从开始直到提交之前，所做的任何修改对其他事务都是不可见的。这个级别有时候也叫做不可重复读（nonrepeatable read），因为两次执行同样的查询，可能会得到不一样的结果。
-
可重复读（Repeatable read）：可重复读解决了脏读的问题。该级别保证了在同一个事务中多次读取同样记录的结果是一致的。但是理论上，可重复读隔离级别还是无法解决另外一个幻读（Phantom read）问题。所谓幻读，指的是当某个事务在读取某个范围内的记录时，另外一个事务中又在该范围插入了新的记录，当之前的事务再次读取该范围的记录时，会产生幻行（Phantom row）。可重复读是MySQL的默认事务隔离级别。
-
可串行化（Serializable）：可串行化是最高的隔离级别。它通过强制事务串行执行，避免了前面所说的幻读问题。简单来说，可串行化会在读取的每一行数据上都加上锁，所以可能导致大量的超时和锁争用问题。实际应用中也很少用到这个隔离级别，只有在非常需要确保数据的一致性而且可以接受没有并发的情况下，才考虑用该级别。
23、慢查询
MySQL慢查询开启，语句分析
一、开启mysql慢查询
方式一:修改配置文件
在 my.ini 增加几行: 主要是慢查询的定义时间（超过2秒就是慢查询），以及慢查询log日志记录（ slow_query_log）
方式二:通过MySQL数据库开启慢查询:
二、查看慢查询的数量
show global status like '%slow%'; 三、分析慢查询日志
直接分析mysql慢查询日志 ,利用explain关键字可以模拟优化器执行SQL查询语句，来分析sql慢查询语句
例如：执行EXPLAIN SELECT * FROM res_user ORDER BYmodifiedtime LIMIT 0,1000得到如下结果：
显示结果分析：
table | type | possible_keys | key |key_len | ref | rows | Extra
-
EXPLAIN列的解释：
-
table 显示这一行的数据是关于哪张表的
-
type 这是重要的列，显示连接使用了何种类型。从最好到最差的连接类型为const、eq_reg、ref、range、indexhe和ALL
24、Mysql调优
1、创建索引（恰当的添加索引）
如果不加索引的话，那么查找任何哪怕只是一条特定的数据都会进行一次全表扫描，如果一张表的数据量很大而符合条件的结果又很少，那么不加索引会引起致命的性能下降。但是也不是什么情况都非得建索引不可，比如性别可能就只有两个值，建索引不仅没什么优势，还会影响到更新速度，这被称为过度索引。
所以要建在合适的地方，合适的对象上。经常操作 / 比较 / 判断的字段应该建索引。
2、适当的用复合索引代替单索引
比如有一条语句是这样的：
select * from users where area=’beijing’ and age=22; 如果我们是在area和age上分别创建单个索引的话，由于mysql查询每次只能使用一个索引，所以虽然这样已经相对不做索引时全表扫描提高了很多效率，但是如果在area、age两列上创建复合索引的话将带来更高的效率。如果我们创建了(area, age,salary)的复合索引，那么其实相当于创建了(area,age,salary)、(area,age)、(area)三个索引，这被称为最佳左前缀特性。
因此我们在创建复合索引时应该将最常用作限制条件的列放在最左边，依次递减。
3、索引不会包含有NULL值的列
只要列中包含有NULL值都将不会被包含在索引中，复合索引中只要有一列含有NULL值，那么这一列对于此复合索引就是无效的。所以我们在数据库设计时不要让字段的默认值为NULL。
4、使用短索引
对串列进行索引，如果可能应该指定一个前缀长度。例如，如果有一个CHAR(255)的 列，如果在前10 个或20 个字符内，多数值是惟一的，那么就不要对整个列进行索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和I/O操作。
5、like语句操作 （不鼓励模糊查询，会全表扫描）
一般情况下不鼓励使用like操作，如果非使用不可，如何使用也是一个问题。like “%aaa%” 不会使用索引而like “aaa%”可以使用索引。
6、不使用NOT IN和操作
NOT IN和操作都不会使用索引将进行全表扫描。NOT IN可以NOT EXISTS代替。
7、开启查询缓存。
避免某些 SQL 函数直接在 SQL 语句中使用，从而导致 Mysql 缓存失效。
query_cache_type【0(OFF)1(ON)2(DEMAND)】来控制缓存的开关. 数据修改会带来缓存失效。
8、表的设计
垂直分割表，使得固定表与变长表分割，从而降低表的复杂度和字段的数目。
9、读写分离方案
海量数据的存储及访问，通过对数据库进行读写分离，来提升数据的处理能力, 数据库的写操作都集中到一个数据库上，而一些读的操作呢，可以分解到其它数据库上。
优点：得数据库的处理压力分解到多个数据库上，从而大大提升数据处理能力 缺点：付出数据复制的成本。
10、缓存技术
搭建redis或者memcache做为缓存层，提高数据库读取速度。
11、Mysql limit 分页机制和优化实例
300W数据，select XXX from tableA limit 1000000,10;会导致mysql将1000000之前的所有数据全部扫描一次，大量浪费了时间。
Solution
查询字段，加索引，可以建立与主键的复合索引 limit最大的问题在于要扫描前面不必要的数据，所以可以先对主键的条件做设定，然后记录住主键的位置再取行。
select * from p2p_20131230 where main_id > 1000000 order by main_id limit 10; 12、增加中间表
对于需要经常联合查询的表，可以建立中间表以提高查询效率。通过建立中间表，把需要经常联合查询的数据插入到中间表中，然后将原来的联合查询改为对中间表的查询，以此来提高查询效率。
25、索引的创建
1、创建索引
在执行CREATE TABLE语句时可以创建索引，也可以单独用CREATE INDEX或ALTER TABLE来为表增加索引。
普通索引、UNIQUE索引或PRIMARY KEY索引区别 如果不允许重复值，则使用UNIQUE索引或PRIMARY KEY索引，否则用普通索引，另外PRIMARY KEY索引是主键索引，一张表只有一个字段是PRIMARY KEY索引。
2、单字段索引创建
ALTER TABLE ALTER TABLE用来创建普通索引、UNIQUE索引或PRIMARY KEY索引。 ALTER TABLE table_name ADD INDEX index_name (column_list) ALTER TABLE table_name ADD UNIQUE (column_list) ALTER TABLE table_name ADD PRIMARY KEY (column_list)
CREATE INDEX CREATE INDEX可对表增加普通索引或UNIQUE索引 CREATE INDEX index_name ON table_name (column_list) CREATE UNIQUE INDEX index_name ON table_name (column_list)
单字段索引删除
DROP INDEX index_name ON talbe_name 3、复合索引创建
ALTER TABLE myIndex ADD INDEX name_city_age (Name(10),City,Age); 为什么是Name(10)？ 一般情况下名字的长度不会超过 10，这样会加速索引查询速度，还会减少索引文件的大小，提高 INSERT 的更新速度。
4、Mysql复合索引符合最左原则：
对于复合索引:Mysql从左到右的使用索引中的字段，一个查询可以只使用索引中的一部份，但只能是最左侧部分。例如索引是key index (a,b,c). 可以支持a | a,b| a,b,c 3种组合进行查找，但不支持 b,c进行查找 .当最左侧字段是常量引用时，索引就十分有效。因此我们在创建复合索引时应该将最常用作限制条件的列放在最左边，依次递减。
5、哪些字段适合作为索引
注明：有两个概念叫做窄索引和宽索引,窄索引是指索引列为1-2列的索引,宽索引也就是索引列超过2列的索引; 设计索引的一个重要原则就是能用窄索引不用宽索引,因为窄索引往往比组合索引更有效;
6、何时用单字段索引
表的主键、外键必须有索引 数据量超过300的应该有索引 经常与其他表进行连接的表，在连接字段上应该建立索引 经常出现在where子句中的字段，特别是大表的字段，应该建立索引 索引应该建立在选择性高的字段上 索引应该建立在小字段上，对于大的文本字段甚至超长字段，不要建立索引 复合索引的简历需要进行仔细的分析；尽量考虑使用单字段索引代替
7、何时是用复合索引
根据where条件建索引是极其重要的一个原则，复合索引的几个字段是否经常同时以AND方式出现在Where子句中？单字段查询是否极少甚至没有？如果是，则可以建立复合索引；否则考虑单字段索引；如果where条件中是OR关系，加索引不起作用。
8、复合索引和多个单列索引的效率比较
比如有一条语句是这样的：
select * from users where area=’beijing’ and age=22; 如果我们是在area和age上分别创建单个索引的话，由于mysql查询每次只能使用一个索引，所以虽然这样已经相对不做索引时全表扫描提高了很多效率，但是如果在area、age两列上创建复合索引的话将带来更高的效率。如果我们创建了(area, age,salary)的复合索引，那么其实相当于创建了(area,age,salary)、(area,age)、(area)三个索引，这被称为最佳左前缀特性。
9、如何使用复合索引与单索引索引？
对于具有2个用and连接条件的语句，且2个列之间的关联度较低的情况下，复合索引有一定优势。 对于具有2个用and连接条件的语句，且2个列之间的关联度较高的情况下，复合索引有很大优势。 对于具有2个用or连接条件的语句，单索引有一定优势，因为这种情况下复合索引将会导致全表扫描，而前者可以用到index merge的优化。
10、索引的建立的注意事项？
频繁进行数据操作（insert、update、delete）的表，不要建立太多的索引； 删除无用的索引，避免对执行计划造成负面影响； 以上是一些普遍的建立索引时的判断依据。一言以蔽之，索引的建立必须慎重，对每个索引的必要性都应该经过仔细分析，要有建立的依据。因为太多的索引与不充分、不正确的索引对性能都毫无益处
在表上建立的每个索引都会增加存储开销，索引对于插入、删除、更新操作也会增加处理上的开销。另外，过多的复合索引，在有单字段索引的情况下，一般都是没有存在价值的；相反，还会降低数据增加删除时的性能，特别是对频繁更新的表来说，负面影响更大。
11、Mysql索引命中规则
往期推荐
宝剑锋从磨砺出，梅花香自苦寒来，我是小码哥为你圆梦大厂少走弯路,值得关注。
干货满满
