@@ -1,58 +0,0 @@ 索引实现 | 凤凰涅槃进阶之路

索引实现

Abel sun2022年12月24日
约 1318 字大约 4 分钟

索引实现

1. 聚簇索引

MyISAM 和 InnoDB 都使用B+Tree索引结构,但底层索引存储不同,MyISAM 采用非聚簇索引,而InnoDB采用聚簇索引

  • 聚簇索引:索引和数据文件为同一个文件
  • 非聚簇索引:索引和数据文件 分开的索引

2. MyISAM 索引原理

2.1 底层存储结构

  • frm:定义表
  • myi: myisam索引
  • myd:myisam数据

2.2 myISAM 索引结构特性

  • 采用非聚簇索引

  • MyISAM myi索引文件和myd 数据文件分离

  • 索引文件仅保存数据记录的指针地址。

  • 叶子节点data域存储指向数据记录的指针地址

2.3 MyISAM 索引查找流程

  • MyISAM 索引按照B+Tree搜索,

  • 如果指定的key存在,则取出其data域值

  • 然后以data阈值-数据地址去读取响应的数据记录,

辅助索引和主索引在结构上没有任何区别,只是主索引要求key 是唯一的,而辅助索引的key 可以重复

image-20190906225153866

3. InnoDB

3.1 InnoDB优势

  • 高扩展性
  • 充分开发硬件性能
  • Crash Safe
  • 支持事务
  • 可以在线热备份

3.2 InnoDB特性

  1. 事务支持(ACID)

  2. 扩展性优良

  3. 读写不冲突

  4. 缓存加速

3.3 组件功能

  • redo/undo
  • 异步IO
  • MVCC
  • 行级别锁
  • Page Cache(LRU)

3.4 InnoDB物理存储结构

image-20190906225909455

  • 表空间(ibd文件)

    • InnoDB 以表空间Tablespace(idb文件)结构进行组织
  • 段(Segment)

    • 每个Tablespce 包含多个Segment段

      分为2种段:叶子节点Segment 和非叶子节点Segment

  • Extent

    • 一个Segment段包含多个Extent

      一个Extent占用占用1M空间包含64个page(每个Page 16K)

  • Page(16K)

    • InnoDB B-Tree 一个逻辑节点扣分配一个物理Page,一个节点一次IO操作
  • Row

    • 一个Page里包含很多有序数据Row行数据
  • Field

    • Row行数据中包含Field 属性数据等信息

3.5 表插入数据扩展原理

一次扩张一个Extent空间(IM),64个page,按顺序结构向每个page中插入数据

3.6 InnoDB 逻辑组织结构

image-20190906233212924

每个索引一个B+Tree,一个B+Tree节点 = 一个物理Page(16K)

数据按16KB切片为Page 并编号,编号可映射到物流文件偏移(16K*N),B+Tree树叶子节点前后形成双向链表,数据按主键聚簇,二级索引叶节点存储主键值,通过叶节点主键值回表查找数据

4. InnoDB 索引原理

4.1 InnoDB 特点

  • 采用聚簇索引

  • InnoDB 数据&索引文件为idb文件,

  • 表数据文件本身就是就是主索引

  • 相邻的索引临近存储。

  • 叶节点data域保存了完整的数据记录(数据[除了主键id外其他data]+主索引)

  • 叶子节点直接存储数据记录,以主键id为key,叶子节点直接存储数据记录

4.2 底层存储结构

  • frm: 表定义
  • idb: innoDB数据&索引文件

4.3 为什么InnoDB 一定要有主键

**由于InnoDB 采用聚簇索引结构存储,索引InnoDB 的数据文件需要按照主键聚集。**因此InnoDB 要求表必须有主键(MyISAM可以没有)。

如果没有指定mysql会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这样的列,mysql自动为innoDB表生成一个隐含字段(6个字节长整型)作为主键。innoDB所有辅助索引都引用数据记录的主键 作为data 域

4.4 辅助索引需要检索两遍

聚簇索引这种实现方式使得主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引

  1. 首先检索辅助索引获得数据记录主键

  2. 然后用主键到主索引中检索获得数据记录

4.5 聚簇索引结构

image-20190906235927601

4.6 索引的查找流程

2.6.1 索引精确查找:

select * from user_info where id = 23
  1. 确定定位条件,找到根节点的PageNo
  2. 根节点读到内存
  3. 逐层向下查找
  4. 读取叶子节点的Page
  5. 通过二分查找找到记录或未命中

image-20190907002116080

2.6.2 索引范围查找

select * from user_info where id >= 18 and id < 22
  1. 读取根节点至内存
  2. 确定索引定位条件 id=18
  3. 找到满足条件第一个叶子节点,
  4. 顺序扫描所有结果,直到终止条件满足id>=22

image-20190907002422372

2.6.3 全表扫描

select * from user_info where name = 'abc'

  1. 直接读取叶子节点头结点
  2. 顺序扫描
  3. 返回符合条件记录,到最终节点结束

image-20190907002631318

2.6.4 二级索引查找

Create table table_x(int id primary key, varchar(64) name,key sec_index(name) )

• Select * from table_x where name = “d”;
  1. 通过二级索引查出主键
  2. 拿主键回表查主键索引得到数据
  3. 二级索引可筛选掉大量无效记录,提高效率

image-20190907002924866

评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.9.1