为了提高mysql的查询效率,通常是建立索引机制来提高数据库的查询效率,但是不同的索引结构使索引的查询到的速度也不一样,mysql的索引机制是采用了树形结构中的B+数,

为了mysql的B+ 树的更好的理解 从二叉树到平衡树到B树再到一个B+树的一个理解笔记  

二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分  。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点 

树形结构比其他的链表结构来说大大的节省了时间,但是树形结构的查询速度不一定.在有些极端的情况下,会很慢,比如:都是右侧的树,或是左侧树,而你要查的数据正好在数据的最底部的时候;这时候就有了比二叉树更好一点的树形结构,平衡二叉树

平衡二叉树

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

当在数据量比较大的时候,树的高度就会变的很高,高度会影响数据的查询效率

B树 (多路平衡树)

B树比二叉树在结构上的改变就是,从一个节点下方的字节点不在是2个节点,可以是多个,这样一来 ,数据结构就从一个瘦高瘦高的瘦子变成了矮胖矮胖的瘦子

m阶的B树满足以下性质：

    （1）每个节点最多拥有m个子树

    （2）根节点最少有2个子树

    （3）分支节点最少拥有m/2棵子树

    （4）所有叶节点都在同一层，每个节点最多有m-1个key，并且以升序排列

B树的插入节点流程

定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

遵循规则：

（1）当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2） -1小于等于5-1（关键字数小于cei(5/2) -1就要进行节点合并，大于5-1就要进行节点拆分,非根节点关键字数>=2）；

（2）满足节点本身比左边节点大，比右边节点小的排序规则;

B树节点的删除

（1）当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于cei(5/2)-1，小于等于5-1，非根节点关键字数大于2；

（2）满足节点本身比左边节点大，比右边节点小的排序规则;

（3）关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放

B+Tree

B+树和B树的不同之处是:

（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，这样使得B+树每个节点所能保存的关键字大大增加；

（2）B+树叶子节点保存了父节点的所有关键字和关键字记录的指针，每个叶子节点的关键字从小到大链接；

（3）B+树的根节点关键字数量和其子节点个数相等;

（4）B+的非叶子节点只进行数据索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样；

mysql数据库引擎

数据库存储引擎：是数据库底层软件组织，数据库管理系统（DBMS）使用数据引擎进行创建、查询、更新和删除数据。不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等功能，使用不同的存储引擎，还可以获得特定的功能。现在许多不同的数据库管理系统都支持多种不同的数据引擎。MySQL的核心就是插件式存储引擎。

查看存储引擎：

我们可以用SHOW ENGINES; 来查询数据库的存储引擎

MySQL给用户提供了许多不同的存储引擎。在MySQL中，不需要在整个服务器中使用同一种存储引擎，针对具体的要求，可以对每一个表使用不同的存储引擎。Support列的值表示某种引擎是否能使用：YES表示可以使用、NO表示不能使用、DEFAULT表示该引擎为当前默认的存储引擎。

我们也可以通过使用命令来查看数据库默认使用的引擎：SHOW VARIABLES LIKE 'storage_engine';

 

InnoDB存储引擎

 

InnoDB是事务型数据库的首选引擎，支持事务安全表（ACID），其它存储引擎都是非事务安全表，支持行锁定和外键，MySQL5.5以后默认使用InnoDB存储引擎。

 

InnoDB主要特性

为MySQL提供了具有提交、回滚和崩溃恢复能力的事务安全（ACID兼容）存储引擎。InnoDB锁定在行级并且也在 SELECT语句中提供一个类似Oracle的非锁定读。这些功能增加了多用户部署和性能。在SQL查询中，可以*地将InnoDB类型的表和其他MySQL的表类型混合起来，甚至在同一个查询中也可以混合。

 

InnoDB表的自动增长列可以手工插入，但是插入的如果是空或0，则实际插入到则是自动增长后到值。可以通过"ALTER TABLE...AUTO_INCREMENT=n;"语句强制设置自动增长值的起始值，默认为1，但是该强制到默认值是保存在内存中，数据库重启后该值将会丢失。可以使用LAST_INSERT_ID()查询当前线程最后插入记录使用的值。如果一次插入多条记录，那么返回的是第一条记录使用的自动增长值。

对于InnoDB表，自动增长列必须是索引。如果是组合索引，也必须是组合索引的第一列，但是对于MyISAM表，自动增长列可以是组合索引的其他列，这样插入记录后，自动增长列是按照组合索引到前面几列排序后递增的。

 

MySQL支持外键的存储引擎只有InnoDB，在创建外键的时候，父表必须有对应的索引，子表在创建外键的时候也会自动创建对应的索引。在创建索引的时候，可以指定在删除、更新父表时，对子表进行的相应操作，包括restrict、cascade、set null和no action。其中restrict和no action相同，是指限制在子表有关联的情况下，父表不能更新；casecade表示父表在更新或删除时，更新或者删除子表对应的记录；set null 则表示父表在更新或者删除的时候，子表对应的字段被set null。

当某个表被其它表创建了外键参照，那么该表对应的索引或主键被禁止删除。

可以使用set foreign_key_checks=0;临时关闭外键约束，setforeign_key_checks=1;打开约束。

 

InnoDB存储引擎为在主内存中缓存数据和索引而维持它自己的缓冲池。InnoDB将它的表和索引在一个逻辑表空间中，表空间可以包含数个文件（或原始磁盘文件）。这与MyISAM表不同，比如在MyISAM表中每个表被存放在分离的文件中。InnoDB表可以是任何尺寸，即使在文件尺寸被限制为2GB的操作系统上。

InnoDB支持外键完整性约束，存储表中的数据时，每张表的存储都按主键顺序存放，如果没有显示在表定义时指定主键，InnoDB会为每一行生成一个6字节的ROWID，并以此作为主键。

使用 InnoDB存储引擎 MySQL将在数据目录下创建一个名为 ibdata1的10MB大小的自动扩展数据文件，以及两个名为 ib_logfile0和 ib_logfile1的5MB大小的日志文件

 

l MyISAM存储引擎

 

MyISAM基于ISAM存储引擎，并对其进行扩展。它是在Web、数据仓储和其他应用环境下最常使用的存储引擎之一。MyISAM拥有较高的插入、查询速度，但不支持事务，不支持外键。

 

MyISAM主要特性：

 

被大文件系统和操作系统支持。

当把删除和更新及插入操作混合使用的时候，动态尺寸的行产生更少碎片。这要通过合并相邻被删除的块，若下一个块被删除，就扩展到下一块自动完成。

每个MyISAM表最大索引数是64，这可以通过重新编译来改变。每个索引最大的列数是16。

最大的键长度是1000字节，这也可以通过编译来改变，对于键长度超过250字节的情况，一个超过1024字节的键将被用上。

BLOB和TEXT列可以被索引。

NULL被允许在索引的列中，这个值占每个键的0~1个字节。

所有数字键值以高字节优先被存储以允许一个更高的索引压缩。

每个MyISAM类型的表都有一个AUTOINCREMENT的内部列，当INSERT和UPDATE操作的时候该列被更新，同时AUTOINCREMENT列将被刷新。所以说，MyISAM类型表的AUTOINCREMENT列更新比InnoDB类型的AUTOINCREMENT更快。

数据文件和索引文件可以放置在不同的目录，平均分配IO，获取更快的速度。要指定数据文件和索引文件的路径，需要在创建表的时候通过DATA DIRECTORY和INDEX DIRECTORY语句指定，文件路径需要使用绝对路径。

每个MyISAM表都有一个标志，服务器或myisamchk程序在检查MyISAM数据表时会对这个标志进行设置。MyISAM表还有一个标志用来表明该数据表在上次使用后是不是被正常的关闭了。如果服务器以为当机或崩溃，这个标志可以用来判断数据表是否需要检查和修复。如果想让这种检查自动进行，可以在启动服务器时使用--myisam-recover现象。这会让服务器在每次打开一个MyISAM数据表是自动检查数据表的标志并进行必要的修复处理。MyISAM类型的表可能会损坏，可以使用CHECK TABLE语句来检查MyISAM表的健康，并用REPAIR TABLE语句修复一个损坏到MyISAM表。

每个字符列可以有不同的字符集。

有VARCHAR的表可以固定或动态记录长度。

VARCHAR和CHAR列可以多达64KB。

使用MyISAM引擎创建数据库，将产生3个文件。文件的名字以表名字开始，扩展名之处文件类型：frm文件存储表定义、数据文件的扩展名为.MYD（MYData）、索引文件的扩展名时.MYI（MYIndex）。

 

MyISAM的表支持3种不同的存储格式：静态(固定长度)表，动态表，压缩表

 

 静态表是默认的存储格式。静态表中的字段都是非变长字段，这样每个记录都是固定长度的，这种存储方式的优点是存储非常迅速，容易缓存，出现故障容易恢复；缺点是占用的空间通常比动态表多。静态表在数据存储时会根据列定义的宽度定义补足空格，但是在访问的时候并不会得到这些空格，这些空格在返回给应用之前已经去掉。同时需要注意：在某些情况下可能需要返回字段后的空格，而使用这种格式时后面到空格会被自动处理掉。

动态表包含变长字段，记录不是固定长度的，这样存储的优点是占用空间较少，但是频繁到更新删除记录会产生碎片，需要定期执行OPTIMIZE TABLE语句或myisamchk -r命令来改善性能，并且出现故障的时候恢复相对比较困难。

压缩表由myisamchk工具创建，占据非常小的空间，因为每条记录都是被单独压缩的，所以只有非常小的访问开支。

 

l MEMORY存储引擎

 

MEMORY存储引擎将表中的数据存储到内存中，为查询和引用其他表数据提供快速访问。

 

MEMORY主要特性：

MEMORY表的每个表可以有多达32个索引，每个索引16列，以及500字节的最大键长度。

可以在一个MEMORY表中有非唯一键值。

MEMORY支持AUTO_INCREMENT列和对可包含NULL值的列的索引。

MEMORY表在所由客户端之间共享（就像其他任何非TEMPORARY表）。

MEMORY表内存被存储在内存中，内存是MEMORY表和服务器在查询处理时的空闲中，创建的内部表共享。

默认情况下，MEMORY数据表使用散列索引，利用这种索引进行“相等比较”非常快，但是对“范围比较”的速度就慢多了。因此，散列索引值适合使用在"="和"<=>"的操作符中，不适合使用在"<"或">"操作符中，也同样不适合用在order by字句里。如果确实要使用"<"或">"或betwen操作符，可以使用btree索引来加快速度。

存储在MEMORY数据表里的数据行使用的是固定长度的格式，因此加快处理速度，这意味着不能使用BLOB和TEXT这样的长度可变的数据类型。VARCHAR是一种长度可变的类型，但因为它在MySQL内部当作长度固定不变的CHAR类型，所以也可以使用。

create table tab_memoryengine=memory select id,name,age,addr from man order by id;

使用USING HASH/BTREE来指定特定到索引。

create index mem_hash using hashon tab_memory(city_id);

在启动MySQL服务的时候使用--init-file选项，把insert into...select或load data infile 这样的语句放入到这个文件中，就可以在服务启动时从持久稳固的数据源中装载表。

每个MEMORY表中放置到数据量的大小，受到max_heap_table_size系统变量的约束，这个系统变量的初始值是16M，同时在创建MEMORY表时可以使用MAX_ROWS子句来指定表中的最大行数。

每个MEMORY表实际对应一个磁盘文件，格式是.frm。MEMORY类型的表访问非常快，因为它到数据是放在内存中的，并且默认使用HASH索引，但是一旦服务器关闭，表中的数据就会丢失，但表还会继续存在。　服务器需要足够的内存来维持所在的在同一时间使用的MEMORY表，当不再需要MEMORY表的内容时，要释放被MEMORY表使用的内存，应该执行 DELETE FROM或 TRUNCATE TABLE，或者删除整个表（使用DROP TABLE）。

mysql的回表

mysql的数据结构是依赖于主键索引的叶子进行存储数据的,当用其他的索引进行查询数据的时候,索引的会查到当前的索引然后返回查主键的索引,被城为会表,如何没有主键,数据会依赖于一个唯一的子段下.