数据库索引 B+树结构和提高效率的原因 引擎区别

电话面试

索引

MySQL官方对索引的定义为： 索引（ Index） 是帮助MySQL高效获取数据的数据结构：索引是数据结构。

B-B+ 树结构

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据

B 树

可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点
根节点至少有两个子节点
每个节点最多有M-1个key，并且以升序排列
位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
其它节点至少有M/2个子节点

B+树

是对B树的一种变形树，它与B树的差异在于：
有k个子结点的结点必然有k个关键码；
非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录

一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。

下图是一个M=4 阶的B树:

B+树

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，形成了带有顺序访问指针的B+Tree。 做
这个优化的目的是为了提高区间访问的性能，

B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B+ 树的优点在于：

由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。下面是B 树和B+树的区别图：

索引与内存

索引本身也很大， 不可能全部存储在内存中， 因此索引往往以索引文件的形式存储的磁盘上。 这样的
话， 索引查找过程中就要产生磁盘I/O消耗， 相对于内存存取， I/O存取的消耗要高几个数量级， 所以评价一个数据
结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。

从局部性原理原理中，数据库系统的设计者巧妙利用了磁盘预读原理， 将一个节点的大小设为等于一个页， 这样每个节点只
需要一次I/O就可以完全载入。

B-Tree中一次检索最多需要h-1次I/O（ 根节点常驻内存） ， 渐进复杂度为O(h)=O(logdN)。
出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

d越大索引的性能越好，
而出度的上限取决于节点内key和data的大小：由于B+Tree内节点去掉了data域， 因此可以拥有更大的出度， 拥有更好的性能

引擎区别

底层：

• InnoDB的数据文件本身就是索引文件.MyISAM索引文件和数据文件是分离的， 索引文件仅保存数据记录的地址。 而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构， 这棵树的叶节点data域保存了完整的数据记录。 这个索引的key是数据表的主键， 因此InnoDB表数据文件本身就是主索引。（数据文件的扩展名为.MYD (MYData)。索引文件的扩展名是.MYI (MYIndex)）

• 与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址

表面：

• InnoDB：行锁设计、支持外键，实现了 SQL 标准的 4 种隔离级别 ,默认为REPEATABLE 级别
  MyISAM：不支持事务、不支持外键、使用表锁和支持全文索引

• MyISAM：如果执行大量的SELECT，MyISAM是更好的选择
  InnoDB：如果你的数据执行大量的INSERT或UPDATE，出于性能方面的考虑，应该使用InnoDB表

• 为什么MyISAM会比Innodb 的查询速度快。
  INNODB在做SELECT的时候，要维护的东西比MYISAM引擎多很多；
  1）数据块，INNODB要缓存，MYISAM只缓存索引块， 这中间还有换进换出的减少；
  2）innodb寻址要映射到块，再到行，MYISAM 记录的直接是文件的OFFSET，定位比INNODB要快
  3）INNODB还需要维护MVCC一致；虽然你的场景没有，但他还是需要去检查和维护