索引原理；为什么采用B+树？

在MySQL中，索引的原理是通过数据结构来快速查找数据。常见的索引数据结构有B树、B+树和哈希表等。MySQL大多数存储引擎（如InnoDB）使用B+树作为索引的数据结构。

为什么采用B+树？

1. B+树结构

• B+树是一种平衡树，它是在B树的基础上进行改进的。B+树的所有叶子节点都在同一层，且叶子节点之间通过指针连接，形成一个链表。
• B+树的非叶子节点只存储索引键及其子节点指针，而叶子节点存储实际数据和索引键。

2. 优势

1. 平衡性：

   • B+树的所有叶子节点都在同一层，保证了树的高度平衡，使得插入、删除和查找操作的时间复杂度都是O(log n)。

2. 范围查询效率高：

   • 由于叶子节点形成了有序链表，B+树非常适合范围查询。可以顺序遍历叶子节点来快速获取范围内的数据。

3. 减少IO操作：

   • 非叶子节点只存储索引键和指针，占用空间小，能存储更多的索引键在内存中，减少了IO操作。
   • 叶子节点存储实际数据，当查询的数据量较小时，只需要访问少量的叶子节点，进一步减少IO操作。

4. 磁盘读写友好：

   • B+树的节点大小通常与磁盘块大小相同，这样可以有效利用磁盘的预读功能，提高读取效率。

5. 适用于数据库的存储模型：

   • 数据库通常涉及大量的读写操作，B+树通过将数据存储在叶子节点，可以更好地支持频繁的数据读写。

B+树和B树的区别

• 结构：

  • B树的所有节点都存储数据，B+树的叶子节点存储数据，非叶子节点只存储索引键。

• 查询效率：

  • B+树更适合范围查询，因为叶子节点形成了链表结构，可以顺序遍历。

• 空间利用率：

  • B+树的非叶子节点只存储索引键和指针，能在内存中存储更多的索引键，提高查询效率。

总之，MySQL选择B+树作为索引的数据结构，主要是因为B+树在查询性能、磁盘读写效率、范围查询支持等方面具有显著优势，能够更好地满足数据库系统对高效数据访问的需求。