b-tree又叫平衡多路查找树（并不是二叉的）使用b-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。
左子节点关键字值<该关键字值<右子节点关键字值
在b-tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。
（key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据）
b+treeb+tree是一种改进后的b-tree。
（key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据）
与b-tree相比，b+tree有以下不同点：
每个节点的指针上限为2d而不是2d+1。
内节点不存储data，只存储key；叶子节点不存储指针。
那数据库为什么使用b-tree计算机的机械磁盘，为了摊还机械移动花费的等待时间，磁盘会一次存取多个数据项而不是一个，这样的一次读取的信息单元是page，我们可以用读或写的页数作为磁盘存取总时间的主要近似值，在任何时刻，b树算法都只需在内存中保持一定数量的页面。b树的设计考虑磁盘预读取这点，一个b树的节点通常和一个完整磁盘页（page）一样大，并且磁盘页的大小限制了一个b树节点可以含有的孩子个数（分支因子），当然这个具体也需要取决于一个关键字相对一页的大小。
为了尽量减少i/o操作，磁盘读取每次都会预读，大小通常为页的整数倍。即使只需要读取一个字节，磁盘也会读取一页的数据(通常为4k)放入内存，内存与磁盘以页为单位交换数据。因为局部性原理认为，通常一个数据被用到，其附近的数据也会立马被用到。
b-tree：如果一次检索需要访问4个节点，数据库系统设计者利用磁盘预读原理，把节点的大小设计为一个页，那读取一个节点只需要一次i/o操作，完成这次检索操作，最多需要3次i/o(根节点常驻内存)。数据记录越小，每个节点存放的数据就越多，树的高度也就越小，i/o操作就少了，检索效率也就上去了。
b+tree：非叶子节点只存key，大大滴减少了非叶子节点的大小，那么每个节点就可以存放更多的记录，树更矮了，i/o操作更少了。所以b+tree拥有更好的性能。
什么是索引索引说白了就是一种数据结构。
索引的代价索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，mysql在运行时也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引
第一种情况是表记录比较少
另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性(selectivity)，是指不重复的索引值(也叫基数，cardinality)与表记录数(#t)的比值
索引的类别一、普通索引
二、唯一索引
三、主键索引
四、组合索引
mysql中使用的索引mysql中普遍使用b+tree做索引，但在实现上又根据聚簇索引和非聚簇索引而不同。
聚集索引与非聚集索引所谓聚簇索引，就是指主索引文件和数据文件为同一份文件，聚簇索引主要用在innodb存储引擎中。在该索引实现方式中b+tree的叶子节点上的data就是数据本身，key为主键。如下图：
（t1表）
（t2表）
（数据库对应的文件）
因为innodb的数据文件本身要按主键聚集，所以innodb要求表必须有主键（myisam可以没有），如果没有显式指定，则mysql系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则mysql自动为innodb表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
mysql数据库中myisam和innodb数据存储引擎主要区别：
myisam是非事务安全型的，而innodb是事务安全型的。
myisam锁的粒度是表级，而innodb支持行级锁定。
myisam支持全文类型索引，而innodb不支持全文索引。
myisam相对简单，所以在效率上要优于innodb，小型应用可以考虑使用myisam。
myisam表是保存成文件的形式，在跨平台的数据转移中使用myisam存储会省去不少的麻烦。
innodb表比myisam表更安全，可以在保证数据不会丢失的情况下，切换非事务表到事务表（alter table tablename type=innodb）。
应用场景：
myisam管理非事务表。它提供高速存储和检索，以及全文搜索能力。如果应用中需要执行大量的select查询，那么myisam是更好的选择。
innodb用于事务处理应用程序，具有众多特性，包括acid事务支持。如果应用中需要执行大量的insert或update操作，则应该使用innodb，这样可以提高多用户并发操作的性能。
补充主存的存取过程
当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。
写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。
这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取a0再取a1和先取a0再取d3的时间消耗是一样的
磁盘存取原理当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
以上就是mysql索引以及结构深入详解的内容。