MySQL数据库——索引结构之B+树

本文先介绍数据结构中树的演化过程，之后介绍为什么MySQL数据库选择了B+树作为索引结构。
  

   
   
  树的演化

• 树
  
  
  
  • 非线性结构，每个节点有唯一的一个父结点和多个子结点（子树），为一对多的关系。
    
  
  
• 二叉树
  
  
  
  • 每个结点最多有两颗子树，并且子树有左右之分，不能颠倒。
    
  
  
• 满二叉树
  
  
  
  • 每一层的结点个数都到达了当层能到达的最大结点数。
    
  
  
• 完全二叉树
  
  
  
  • 除了最下面一层之外，其余层的结点个数都到达了当层能到达的最大结点数，且最下面一层只从左至右连续存在若干结点，右边的结点全部不存在。
    
  
  
• 二叉查找树 (BST)
  
  
  
  • 又称为二叉排序树、二叉搜刮树。
    
  • 定义：
    
    
    • 要么二叉査找树是一棵空树。
      
    • 要么二叉查找树由根结点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，其中：
      
      
      
      • 左子树的所有结点值小于或等于根节点值
        
      • 右子树的所有结点值大于根节点值。
        
      
      
    
    
  
  
• 均衡二叉树 (AVL 树)
  
  
  
  • 特别的二叉查找树，左右子树都是均衡二叉树，且左右子树高度之差不超过 1。
    
  
  
• B 树
  
  
  
  • 又名均衡多路查找树。每个节点包含多个数据及指针域，查找路径有多个分支。B-树就是 B 树（别讲什么B减树，‘-’是分隔符）。
    
  
  
• B+ 树
  在 B 树底子上发展而来的均衡多路查找树，非叶子节点只存储键值和指针，所有数据存储在叶子节点，并通过链表连接。
  优化主要体现在以下几个方面：
  
  
  
  • 非叶子节点不存储数据，更适合磁盘存储和 I/O 优化
    
    
    
    • B 树：所有节点都存储键值和数据。
      
    • B+ 树：非叶子节点只存储键值和指针，不存储实际数据，使得内部非叶子节点更小，单个磁盘块可容纳更多键值，淘汰树的高度和磁盘 I/O 次数，低落树的高度。
      
    
    
  • 叶子节点存储所有数据，更便于次序遍历，查找效率稳固
    
    
    
    • B 树：数据分散在各个节点，遍历需要中序遍历整棵树。 查询大概在任何节点竣事，查询效率不稳固。
      
    • B+ 树：所有数据存储在叶子节点，并通过链表连接，范围查询、排序查询更高效，可以快速次序遍历数据，无需回溯，所有查询终极都在叶子节点竣事，查找效率稳固。
      
    
    
  
  

为什么其他树结构不行？

磁盘读写的特性：

• 数据库的索引及数据存储在磁盘中，而不是内存中，磁盘 I/O 的速度远慢于内存。
  
• 从磁盘读取数据时，按照磁盘块（页）读取，每次读取的最小单位是一个磁盘块。
  
• 若能将更多数据放入一个磁盘块中，一次读取操作可以获取更多数据，从而淘汰 I/O 次数，进步查询效率。
  

为什么不使用二叉查找树（BST）？

• 大概出现链表形态：二叉查找树在数据不均衡时大概退化成一条链表，类似于全表扫描，查找时无法发挥二叉排序树的优势。
  
• 高度过高：树的高度过高时，查找效率变得不稳固，查询需要遍历较多的节点，导致性能下降。
  

为什么不使用均衡二叉树（AVL树）？

均衡二叉树通过自均衡解决了BST高度过高，查找效率不稳固的问题。但是：

• 节点存储限制：均衡二叉树每个节点只能存储一个键值和数据，对于海量数据，节点数目会非常多，树的高度依然大概较高。
  
• 效率低落：对于大量数据的存储和查找效率依然不理想，因为节点存储量有限，高度无法有效缩减。
  

为什么不使用B树？

B树每个节点有更多子节点，淘汰了树的高度，从而进步了IO性能。解决了均衡二叉树只能存储一个键值和数据的问题。但是：

• 遍历效率低：尽管B树进步了IO性能，但在查找数据时，仍然需要遍历整个树，导致遍历效率低，不同的点查询效率不一样，即查询效率不稳固。
  

为什么选择 B+ 树

• 二叉查找树：大概退化为链表，查找效率不稳固。
  
• 均衡二叉树：固然能包管均衡，但对于海量数据，节点数仍多，高度过高。
  
• B树：进步了IO性能，解决了均衡二叉树的问题，但遍历效率不敷，特别是对于大范围查询。
  

引入B+树：为了进一步进步遍历效率，B+树在B树的底子上做了优化：
1. B+ 树节点结构

• 非叶子节点仅存储键值，不存储数据，节点更紧凑。
  
• 数据只存储在叶子节点，叶子节点通过双向链表串联形成线性表。查询时只需要扫描叶子节点，从而大幅进步了范围查询和排序查询的效率。
  
• 数据库页的大小固定（如 InnoDB 默认 16KB），更高阶数的树更矮更胖，淘汰了磁盘 I/O 次数。
  

2. 优点

• 磁盘读写代价更低：
  
  
  
  • 内部节点不存储数据，节点更小，单个磁盘块可容纳更多键值。
    
  • 淘汰树的高度，相同数据量下 I/O 次数更少。
    
  
  
• 查询效率更加稳固：
  
  
  
  • 查询路径固定，从根节点到叶子节点的路径长度同等，每次查询效率相同。
    
  
  
• 更便于遍历：
  
  
  
  • 数据全部存储在叶子节点，次序遍历时只需扫描叶子节点即可。
    
  • 非叶子节点均为索引，便于范围查询和排序。
    
  
  
• 更适合范围查询：
  
  
  
  • 叶子节点通过链表连接，直接支持高效的范围查询和排序操作。
    
  • 在数据库中，基于范围的查询非常频仍，而 B 树不支持或效率较低。
    
  
  

---

举例

磁盘页大小：默认是 16 KB，也就是16,384 字节（1 KB = 1024 字节）。
假设条件：
2. 每个键值的大小：假设每个键值的大小是 16 字节。
3. 每个节点存储的键值数目：每个磁盘页可以存储 1024 个键值。

• 如果一个节点可以存储 1000 个键值时（没有超过1024 个键值），3 层的 B+ 树可以存储约 10 亿条数据。
  
• 根节点常驻内存，那么查找 10 亿条数据时只需 2 次磁盘 I/O。
  

---

Q&A

Hash比B+树更快，为什么Mysql用B+树来存储索引呢？

首先在功能上：

• B+树可以进行BETWEEN范围查询，Hash索引不能。
  
• B+树支持order by排序，Hash索引不支持。
  
• B+树使用like 进行模糊查询的时候，like后面（比如%开头）的话可以起到优化的作用，Hash索引根本无法进行模糊查询。
  
• B+树支持 InnoDB、MyISAM 和 Memory，Hash索引仅支持Memory（默认情况）
  
• B+树支持团结索引的最左侧原则，Hash索引不支持。
  
• Hash索引在等值查询上比B+树效率更高。
  

从计划上来看：

• 从内存角度上说，数据库中的索引一般时在磁盘上，数据量大的情况大概无法一次性装入内存，B+树的计划可以允许数据分批加载。
  
• 从业务场景上说，等值查询那确实是hash更快，但是数据库中经常会进行排序和范围查询，B+树叶子节点通过双向链表串联形成线性表，它的查询效率比hash就快很多了，hash还需要解决辩说。
  

增加树的路数可以低落树的高度，那么无限增加树的路数是不是可以有最优的查找效率？

答：如许会形成一个有序数组，文件系统和数据库的索引都是存在硬盘上的，并且如果数据量大的话，不愿定能一次性加载到内存中。有序数组没法一次性加载进内存，这时候B+树的多路存储威力就出来了，可以每次加载B+树的一个结点，然后一步步往下找。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。