概要
- B- Tree B+ Tree数据结构相关的理论知识
- MySQl索引的实现
- 索引使用及优化
数据结构和算法
###B- tree 和B+ tree
B-tree
树的度为d（d是大于1的正整数） 高度为h 则每个非叶子节点中含有 n个指针和 n-1个key。其中 d<=n<=2d 一个节点中包含 key,data,pointer 当为3叉树或3阶(最多有3个子节点) key的最小为0个 最多为2个。除了存放key和指向子节点指针外还存了data数据 下图就是 出度 d=2的B- tree图
在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。B-Tree上查找算法的伪代码如下：
BTree_search(Node node,Key key){
if(node == null) return null;
foreach(node.key){
if(node.key[i] == key) return node.data[i];
if(node.key[i] > key) return BTree_search(poniter[i].node,key);
}
return BTree_search(poniter[i+1].node,key);
}
data = BTree_search(root,key);
例如一个度为d的B-Tree，设其索引N个key，检索一个key，其查找节点个数的渐进复杂度为 logdN。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。其中比红黑树或二叉树效率要高 log2N
B+tree
B+ tree就是B- tree的一个变种树 树的度为d 高度为h 则每个非叶子节点中含有 n个指针和 n-1个key 其中 d<=n<2d B+ tree示意图
其中data域在叶子节点中但不包括指针，非叶子节点中只包含key和pointer。由于并不是所有节点都具有相同的域，因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。
一般来说，B+Tree比B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下面讨论。
带顺序访问指针的 B+ tree示意图
当数据库使用区间查询时，这种方式很高效，如果查询出 key在18-50的数据，只需要找到18后，顺着指针就可以获取所有满足条件的数据，极大提高了区间查询效率
为什么使用B+ tree做索引数据结构
前面说了B+ tree中内节点只存放key和pointer,这样保证了在相同页(内存、磁盘中最小分配的单位，和应用程序逻辑页相对应)的大小 减少了data域情况下进而ponitor可以指向更多的子节点，树的出度增加了，其中根节点是一直在内存中，因此最多会发生 O(n) = (logdN)-1 次I/O，(一般数据库中d=100 若高度为3则总的数据量N为1000000) 当N一定时 出度d越大 树的深度就越小，树的深度决定了发生I/O的次数，因此这也减少了发生I/O的次数，提高查询性能。 由于数据库中的索引是以文件形式存放在硬盘中，当文件大的时候不可能全部加载到内存中，因此会出现页面置换的情况，此时就会发生磁盘I/O。为了和内存块相对应也会把磁盘划分成相应大小的页面(4kB),每次创建一个新的节点时则大小规定为页的大小。
可能会问在内存中如何知道该页对应磁盘中的地址，又该从哪里去获取页的数据和调出时放在那个地方？
其实在进程从磁盘中把程序代码加载到内存中，当通过逻辑地址转换对应的页号->对应的块号*页的大小+页内地址=内存物理地址。如果该页不存在内存中，此时就会根据这个逻辑地址到磁盘中获取（原理和映射到内存地址差不多，也需要存放页号和块号映射关系）起始地址位置并往后连续读取一页或几页数据加载到内存中，此时页表项会有 页号 块号 外存地址(磁盘块号) 状态位 修改位 访问位
其实swap区就是内存和外存交换数据的地方，磁盘空间分为文件区：存放各个文件的，对换区：就是用来和内存交换数据的。由于文件区存放的位置是离散的，而交换区是顺序存放的，所以操作交换区的效率更高。各个系统实现方式不一样。
第一种 如果swap足够大时会将所有，在运行之前会将进程的所有页面从文件夹copy到交换区，当发生缺页中断和页面调出时会从swap调入数据
第二种 交换区存放修改过的页面，对于没有修改的页面会从文件区调入，这当页面置换时省去了把数据回写到交换区
第三种 当页面第一次使用时则从文件区调入，后面的调入和调出都是操作交换区，UNIX在使用这种方式
- 主存存取原理：
内存是由各个存储单位组成的，每个单位都会有地址的，可以通过数据总线和地址总线来控制对内存写入和读取，当存入某个数据时，传地址到地址总线，值送到数据总线，然后由内存进行将地址和数据存入。 读取时只需要传地址到地址总线，然后在数据总线获取 数据。其中读取或存入内存的效率和存入或读取的顺序无关，只和访问次数有关，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的
- 磁盘存取原理
磁盘由其由磁头，盘面(划分成多个同心圆称为磁道，又把磁道被沿半径线划分成一个个小的段，这个称为扇区区，磁盘存储的最小单元)等组成。 当想从磁盘读取数据时，传入一个逻辑地址，然后由磁盘电路计算出对应物理地址(对应在那个磁道和那个分区)。 这时会移动磁头，移动 到对应的磁道上，消耗的时间称为寻道时间，同时会旋转盘面，让对应的分区在磁头上，消耗的时间称为旋转时间，其中写入数据也是一样的(如果是顺序写入或顺序读取就省去了寻道时间，只需适当的旋转盘面就行，效率会更高些)。 由于存储介质的特性，磁盘本身存取就比主存慢很多,再加上磁盘获取或写入时是机械运动，非常耗时的操作。所以应该减少磁盘I/O操作，磁盘的存取速度往往是主存的几百分分之一
磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理 局部性原理：
1、空间局部性： 如果某行代码被执行，那么附近的一些代码将来也会被访问 2、时间局部性： 如果某个指令被执行，那么将来有可能会被重复执行，例如程序的循环
其中当从磁盘中获取页面时，可以将此页附近的几个页也一起加载到内存中，以防后面将会访问到，减少磁盘I/O次数
##索引的实现
MyISAM索引实现
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。 MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分
InnoDB索引实现
第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。
上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集和其他二级索引中的data都是引用主键的，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域，以下是辅佐索引
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
为了减小索引空间，则主键不要定义太大，当增加一条数据时，索引为了保证B+ tree的特性如果这主键是随机的，则会导致节点频繁的分裂，十分低效，但是如果是顺序生成的自动增长的主键，那么只需要在最后一条数据后追加一条就行。所以建议使用自动增长主键
###联合索引
create index INDEX_A_B on t(a,b)
联合索引的建立首先会根据 字段a进行排序，然后再根据b列排序，所以在a相等情况下，会进行对b排序。 因此使用联合索引时必须满足前缀的条件，在要使用b列索引 a列索引必须使用而且是精确的一个值例如 a=8。因为只有保证a相等的情况下b列才是有序的。
##索引使用及优化
explain是分析sql执行的情况，是否用到了索引，执行时间如何等
KEY:NULL表示没有使用索引，否则会返回索引名字，主键就是PRIMARY POSSIBLE_KEY 可能使用的索引 select_type:SIMPLE type:const 表示使用了条件值是单值，rnage：表示使用了一个范围，例如 a in (1,8,188) 或 a between 1 and 188, 188=>a>=1
rows:为了获得结果，需要从多少条数据筛选出符合条件的数据，此值越大说明就没有用到索引,或者说此索引建立的没有价值 key_len:表示此sql使用到那些索引列，越小越好。如果没有使用到索引时值为NULL
###最左前缀原理与相关优化
其中 a列是int 大小为4个字节 b为varchar(18)
create index INDEX_A_B on t(a,b)
1、全列匹配
explain select * from t where a=1 and b=’test’; 和 explain select * from t where b=’test’and a=1 ; 效果一样都会使用全部索引列，数据库的查询优化器在执行之前会对自动调整where子句条件顺序 如果所有列都进行精确匹配（（这里精确匹配指“=”或“IN”匹配）时，）此时key_len为32
2、最左前缀匹配
explain select * from t where a=1
key_len为4，说明只用到了索引的第一列前缀
3、查询条件用到了索引中列的精确匹配，但是中间某个条件未提供
若建立的联合索引列是3个列 a、b、c 条件为 a=1 and c=3此时只使用到索引列a 为了全部都使用上 则需要填补 b这个坑 a=1 and b in(所有b列的值) c=3 ，如果b列数据太多则需要考虑再建一个 a、c 联合索引
4、查询条件没有指定索引第一列
如果没有指定索引第一列则显然使用不上索引
5、模糊匹配
explain select * from t where a=1 and b=’test’; 和 explain select * from t where a=1 and b like ‘test%’ 会使用b列部分前缀索引，若果%放在前面就不能使用索引
6、范围查找
explain select * from t where a>1 and b=’test’; 只会使用前缀索引a后面的索引列都不能使用上，可以结合联合索引的数据结构分析
那就是仅用explain可能无法区分范围索引和多值匹配，因为在type中这两者都显示为range。同时，用了“between”并不意味着就是范围查询，例如下面的查询： select * from t where a=3 and b between ‘a’ and ‘b’ 此时可以使用到全部索引列
但作用于b上的“BETWEEN”实际上相当于“IN”，也就是说b实际是多值精确匹配
7、查询条件中含有函数或表达式
explain select * from t where a=1 and left(b,6)=’test’ explain select * from t where a-1=1 第一条sql不能使用索引列b因为其包含了函数，第二条不能使用索引列，因为包含了表达式
8、覆盖索引：例如辅佐索引列为b 主键列为a select a from t where b=1 就是覆盖性索引。就是直接可以通过索引获取想要查询的结果，无需通过id从外存加载实际数据(I/O)
9、索引 a和联合索引 （a,b） select a from t where a=3 order by b,此时数据库会使用上联合索引，因为在a相等情况下对b已经排好序了，order by直接使用，但是如果删除联合索引则只能查询时使用a索引，排序时只好对结果进行filesort,效率肯定没有使用排好序的索引高
10、联合索引 create index index_a_b on t(a,b) select a from t where b=3 此时不会使用到索引，因为不是最左前缀。 如果select count() from t where b=3 那么就会使用到索引 index_a_b,因为count() 需要扫描整个索引才能更快的获取结果，当有主键和辅佐索引时,数据库会选择辅佐索引列进行扫描，因为这样代价更低,相比主键索引列(索引中data是表中的所有字段的数据,辅佐索引为主键id)使用更少的I/O
###索引选择性与前缀索引
另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality）与表记录数（#T）的比值：
Index Selectivity = Cardinality / #T
显然选择性的取值范围为(0, 1]，选择性越高的索引价值越大，所以在建立索引时需要看看该列的选择性
有一种与索引选择性有关的索引优化策略叫做前缀索引，就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。
如果频繁按名字搜索员工，这样显然效率很低，因此我们可以考虑建索引。有两种选择，建
SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;结果为0.042
SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees; 结果为 0.9313