概述
本文主要从参考 某博主关于索引的介绍，记录为什么选用B-+树进行索引，并且数据库设计者做了哪些巧妙的设计。
数据读取基础
内存（主存）读取
一句话总结：内存读取速度很快，并且存取时间仅与读取次数有关，与数据存放位置并无关系，不存在机械操作。
外存（磁盘）读取
外存读取速度相对较慢。磁盘IO需要进行机械操作（磁头寻道和磁盘旋转），这个过程耗费的时间是巨大的。而且存取一批数据，顺序读写比随机读写效率高。相比之下内存存取时间可以忽略不计。
预读机制
为了提高磁盘存取的效率，根据数据局部性原理（程序运行期间访问的数据被认为会比较集中）计算机读取磁盘会有预读机制。即即使只需要一个字节数据，磁盘也会顺序读取一定的长度数据放入内存中，这样可以避免多次磁盘读写。
预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k，实际交换时以4k的整数倍进行存取，比如16k,24k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
B/B+树性能分析
因为索引一般也会比较大，并不是永驻内存的，索引还是会存储在磁盘上。所以索引检索需要磁盘IO，而磁盘IO耗时较长，那么尽量少的磁盘IO对检索效率来讲就很关键。
B树分析：
检索一次B树，需要至少访问N个节点。数据库系统设计者巧妙利用数据预读机制做了如下设计。
- 将一个节点的空间大小设为一个页的大小。这样每次访问节点时，只需要一次IO就可以完全载入。
- 每次新建节点，直接申请一个页的空间，这样就保证一个节点的索引数据，物理上也是存放在一起的。
这样在B树上进行一次检索最多需要H-1次磁盘IO（H为树的高度，其中根节点永驻内存，不占用IO）。实际使用中H一般会比较小（通常不超过3）。
B+树分析：
B+树处包含以上设计外，由于其结构特性。其内节点可以存放更多的索引，有更多的出度（子节点），从而使树的高度更小，磁盘IO次数更少，进而理论上性能更好。
存取性能估计
以B+树为例，假如索引字段类型为BIGINT，占8bit，指向下一个节点的地址指针为6bit（MySQL中分配）一个节点的大小是16K（MySQL中），那么一个节点中可以存放（16K/(8+6)b=1170）个索引。叶子节点有索引有data元素，假设占1K，那一个节点就放16K/1K=16个元素，假设树高是3，所有节点都放满（1170 × 1170 × 16=21902400），可以放2千多万，这种情况下仅需要两次IO就能在两千多万中找到数据。
网友评论