B-Tree结构
一个d=2的B-Tree示意图
B-Tree的数据结构：
1.有一个大于1的正整数d 是B-Tree的度
2.有一个正整数h代表树高
3..每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d
4.每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null
5.所有叶节点具有相同的深度，等于树高h。
6.key和指针互相间隔，节点两端是指针
7.一个节点中的key从左到右非递减排列。
8.每个指针要么为null，要么指向另外一个节点。
B+Tree结构
B+Tree
通过图我们可以看到 B+Tree的非叶子节点不存储data，只存储key。叶子节点存储data，并且叶子节点没有指针。
B-/+Tree索引的性能分析
B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）
MYSQL 中MyISAM索引引擎特点
MyISAM表的主索引（Primary key）示意
我们可以看到MyISAM使用B+Tree作为索引结构，同时叶子节点存储的是数据存放的地址。
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示
辅助索引
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。（不过我猜测估计也是因为它的数据没有直接聚集在索引文件上 我自己乱说的）
MYSQL 中InnoDB索引引擎特点
InnoDB主索引（同时也是数据文件）的示意图
InnoDB的最大区别就是，叶子节点直接存储了数据内容。也就是索引文件和数据文件在一起。这种索引叫做聚集索引
因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址；辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
选用过长的字段作为主键好还是不好？为什么？
不好，因为如果选用过长的字段作为主键，那么辅助索引的叶子节点都是引用主键的，使得辅助索引过大。
InnoDB上采用自增字段做主键好不好？为什么？
好 因为同一个叶子节点内的记录是按主键的顺序存放的。如果采用自增的主键，那么有新纪录插入就可以按照节点的顺序插入。这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。
如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：
随机主键
此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
联合索引生效规则
组合索引的生效原则是 从前往后依次使用生效，如果中间某个索引没有使用，那么断点前面的索引部分起作用，断点后面的索引没有起作用；
比如
where a=3 and b=45 and c=5 .... 这种三个索引顺序使用中间没有断点，全部发挥作用；
where a=3 and c=5... 这种情况下b就是断点，a发挥了效果，c没有效果
where b=3 and c=4... 这种情况下a就是断点，在a后面的索引都没有发挥作用，这种写法联合索引没有发挥任何效果；
where b=45 and a=3 and c=5 .... 这个跟第一个一样，全部发挥作用，abc只要用上了就行，跟写的顺序无关
(0) select * from mytable where a=3 and b=5 and c=4;
abc三个索引都在where条件里面用到了，而且都发挥了作用
(1) select * from mytable where c=4 and b=6 and a=3;
这条语句列出来只想说明 mysql没有那么笨，where里面的条件顺序在查询之前会被mysql自动优化，效果跟上一句一样
(2) select * from mytable where a=3 and c=7;
a用到索引，b没有用，所以c是没有用到索引效果的
(3) select * from mytable where a=3 and b>7 and c=3;
a用到了，b也用到了，c没有用到，这个地方b是范围值，也算断点，只不过自身用到了索引
(4) select * from mytable where b=3 and c=4;
因为a索引没有使用，所以这里 bc都没有用上索引效果
(5) select * from mytable where a>4 and b=7 and c=9;
a用到了 b没有使用，c没有使用
(6) select * from mytable where a=3 order by b;
a用到了索引，b在结果排序中也用到了索引的效果，前面说了，a下面任意一段的b是排好序的
(7) select * from mytable where a=3 order by c;
a用到了索引，但是这个地方c没有发挥排序效果，因为中间断点了，使用 explain 可以看到 filesort
(8) select * from mytable where b=3 order by a;
b没有用到索引，排序中a也没有发挥索引效果
MYSQL有哪些优化技巧
1.避免使用select*，用什么取什么
2.当只要一行数据时使用LIMIT 1
当你查询表的有些时候，你已经知道结果只会有一条结果，单因为你可能需要去fetch游标，或是你也许会去检查返回的记录数。
在这种情况下，加上LIMIT 1 可以增加性能。这样一样， MySQL数据库引擎会在找到一条数据后停止搜索，而不是继续往后查找下一条符合记录的数据。
下面的示例，只是为了找一下是否有“中国”的用户，很明显，后面的会比前面的更有效率。（请注意，第一条中是Select *，第二条是Select 1）
// 没有效率的：
$r = mysql_query("SELECT * FROM user WHERE country = 'China'");
if (mysql_num_rows($r) > 0) {
// ...
}
// 有效率的：
$r = mysql_query("SELECT 1 FROM user WHERE country = 'China' LIMIT 1");
if (mysql_num_rows($r) > 0) {
// ...
}
3.尽可能的使用 NOT NULL
不要以为 NULL 不需要空间，其需要额外的空间，并且，在你进行比较的时候，你的程序会更复杂。 当然，这里并不是说你就不能使用NULL了，现实情况是很复杂的，依然会有些情况下，你需要使用NULL值。
下面摘自MySQL自己的文档
“NULL columns require additional space in the row to record whether their values are NULL. For MyISAM tables, each NULL column takes one bit extra, rounded up to the nearest byte.”
4.为经常使用的搜索字段建索引
5.不要在数据很大的字段上建立索引
6.使用连接（JOIN）来代替子查询(Sub-Queries)
连接（JOIN）.. 之所以更有效率一些，是因为MySQL不需要在内存中创建临时表来完成这个逻辑上的需要两个步骤的查询工作。
7.尽量在多个条件的时候，把会提取尽量少数据量的条件放在前面，减少后一个where条件的查询时间。
MYSQL大数据量分页优化怎么做？
比如你要查询 300w开始后面10条数据；mysql会读取300w加10条这么多的数据，只不过 过滤后返回最后10条而已！！！
select * from table limit 3000000,10;
在查询下一页时把上一页的行id作为参数传递给客户端程序，然后sql就改成了
select * from table where id>3000000 limit 10;
这条语句执行也是在毫秒级完成的，id>300w其实就是让mysql直接跳到这里了，不用依次在扫描全面所有的行
如果你的table的主键id是自增的，并且中间没有删除和断点，那么还有一种方式，比如100页的10条数据
还有一种方法延迟关联:
把前面的select * 变成 select id 把拿到的id再去分别查询其他字段
select table.* from table inner join ( select id from table limit 3000000,10 ) as tmp on tmp.id=table.id;
什么是索引选择性?
索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality）与表记录数（#T）的比值：
Index Selectivity = Cardinality / #T
显然选择性的取值范围为(0, 1]，选择性越高的索引价值越大，这是由B+Tree的性质决定的。
我是这样理解的，因为如果这个比值很小 代表 表中的记录大多数都是重复的。那么建立索引也不能起到区分这条数据和别的数据的作用。在这一列上来说，相反如果不重复的值很多，那么建立索引就能很快找到这条记录了。
什么时候该建立索引 什么时候不应该?
第一种情况是表记录比较少，例如一两千条甚至只有几百条记录的表，没必要建索引，让查询做全表扫描就好了。至于多少条记录才算多，这个个人有个人的看法，我个人的经验是以2000作为分界线，记录数不超过 2000可以考虑不建索引，超过2000条可以酌情考虑索引。
另一种不建议建索引的情况是索引的选择性较低
MYSQL数据库事务四大特性
⑴ 原子性（Atomicity） 原子性是指事务包含的所有操作要么全部成功，要么全部失败回滚，因此事务的操作如果成功就必须要完全应用到数据库，如果操作失败则不能对数据库有任何影响。
⑵ 一致性（Consistency） 一致性是指事务必须使数据库从一个一致性状态变换到另一个一致性状态，也就是说一个事务执行之前和执行之后都必须处于一致性状态。
拿转账来说，假设用户A和用户B两者的钱加起来一共是5000，那么不管A和B之间如何转账，转几次账，事务结束后两个用户的钱相加起来应该还得是5000，这就是事务的一致性。
⑶ 隔离性（Isolation） 隔离性是当多个用户并发访问数据库时，比如操作同一张表时，数据库为每一个用户开启的事务，不能被其他事务的操作所干扰，多个并发事务之间要相互隔离。
即要达到这么一种效果：对于任意两个并发的事务T1和T2，在事务T1看来，T2要么在T1开始之前就已经结束，要么在T1结束之后才开始，这样每个事务都感觉不到有其他事务在并发地执行。
关于事务的隔离性数据库提供了多种隔离级别。
⑷ 持久性（Durability）
持久性是指一个事务一旦被提交了，那么对数据库中的数据的改变就是永久性的，即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。
MYSQL数据库事务隔离级别以及对应级别下能解决的问题
四种隔离级别
MYSQL默认是可重复读
脏读
就是在一个事务的处理过程中读取到了另一个事务未提交的数据。
比如：A向B转账100元，然后查询B账户多了100元，之后转账操作未提交发生回滚，再次查询B账户钱又没有了。
不可重复读
一次事务范围内多次查询同一个数据项，发现前后查询的数值不一致。
幻读
一次事务范围内多次查询一个范围的数据，发现前后查询的数据条数不一样。多了几行或者少了几行
函数依赖 完全函数依赖 部分函数依赖 传递函数依赖的概念
函数依赖
若在一张表中，在属性（或属性组）X的值确定的情况下，必定能确定属性Y的值，那么就可以说Y函数依赖于X，写作 X → Y
比如姓名函数依赖于学号 姓名→学号 因为一个学号对应一个姓名，但是反过来就不是。同名的两个学生，学号不同。
完全函数依赖
在一张表中，若 X → Y，且对于 X 的任何一个真子集（假如属性组 X 包含超过一个属性的话），X ' → Y 不成立，那么我们称 Y 对于 X 完全函数依赖
（学号，课名） F→ 分数 （注：因为同一个的学号对应的分数不确定，同一个课名对应的分数也不确定）
部分函数依赖
假如 Y 函数依赖于 X，但同时 Y 并不完全函数依赖于 X，那么我们就称 Y 部分函数依赖于 X，记作 X P→ Y
（学号，课名） P→ 姓名 比如姓名就只依赖于学号，并不是依赖于这个属性组
传递函数依赖
如 Z 函数依赖于 Y，且 Y 函数依赖于 X （严格来说还有一个X 不包含于Y，且 Y 不函数依赖于Z的前提条件），那么我们就称 Z 传递函数依赖于 X ，记作 X T→ Z
主属性 非主属性 码的概念
码
设 K 为某表中的一个属性或属性组，若除 K 之外的所有属性都完全函数依赖于 K（这个“完全”不要漏了），那么我们称 K 为候选码，简称为码
例如：
表3
对于表3，（学号、课名）这个属性组就是码。该表中有且仅有这一个码。（假设所有课没有重名的情况）
主属性
包含在任意一个码中的属性称为主属性
非主属性
不包含在任何一个码中的属性称为非主属性
MYSQL三大范式
1NF
1NF的定义为：符合1NF的关系中的每个属性都不可再分。表1所示的情况，就不符合1NF的要求。
表1
1NF是所有关系型数据库的最基本要求
2NF
2NF在1NF的基础之上，消除了非主属性对于码的部分函数依赖
3NF
3NF在2NF的基础之上，消除了非主属性对于码的传递函数依赖
参考文章：
MySQL索引背后的数据结构及算法原理
mysql优化小技巧
mysql 大数据量分页优化
mysql 多列索引的生效规则
数据库第一二三范式到底在说什么？
网友评论