MySQL的索引 B＋Tree

MySQL的索引 B+Tree

1. 常见索引的数据结构

哈希(Hash)

示意图

效率高，但是因为Hash算法的特性，数据无序，不能进行范围搜索

二分搜索树(Binary Search Tree)

示意图

数据有序，能够按范围查找，但是容易造成部分数据倾斜，导致该部分数据查询较慢

平衡二分搜索树(Balanced Binary Search Tree, AVL Tree)

示意图

是二分搜索树的优化版，解决了数据倾斜的问题，但是需要维护树平衡的额外开销

B树(B Tree)

示意图

每个节点可以存多条数据，子节点数量也可以大于2，优化了树的深度

B+树(B+Tree)

示意图

叶子节点会额外存储指向相邻叶子节点的指针，优化B树范围查询效率，且更加稳定

2. MySQL中B+Tree的使用

MySQL采用B+Tree，其关键点如下：

非叶子节点存索引，控制树的深度

叶子节点存数据，以及指向相邻叶子节点的指针

数据存入硬盘，需控制每一份数据的大小，以适应硬盘分页

那么每一份数据应该存多大呢？

MySQL每一份数据是硬盘分页大小的倍数

系统从硬盘中进行读取操作，是按页读取的（例如1024k、2048k……）

如果MySQL每一份数据的大小比硬盘一页的量小，那么每次硬盘读取就可能会读取一些不需要的数据，影响性能

通过 SHOW GLOBAL STATUS LIKE 'Innodb_page_size';即可查看MySQL每份数据的大小

3. MySQL中两大主要引擎的索引

MyISAM（非聚集索引）

索引和数据分开存

主键索引(Primary Key): 直接根据索引找到值

辅助索引(Secondary Key): 直接根据索引找到值

InnoDB（聚集索引）

索引和数据存一起（必须有一个索引，没有会建一个默认的）

主键索引(Primary Key): 直接根据索引找到值

辅助索引(Secondary Key): 先用索引找到主键，再根据主键找到值

山东掌趣网络科技