Java学习笔记

索引实现

zszdevelop数据库大约 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
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
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
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
image-20190906235927601

4.6 索引的查找流程

2.6.1 索引精确查找：

select * from user_info where id = 23
  1. 确定定位条件，找到根节点的PageNo
  2. 根节点读到内存
  3. 逐层向下查找
  4. 读取叶子节点的Page
  5. 通过二分查找找到记录或未命中。
image-20190907002116080
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
image-20190907002422372

2.6.3 全表扫描

select * from user_info where name = 'abc'

  1. 直接读取叶子节点头结点
  2. 顺序扫描
  3. 返回符合条件记录，到最终节点结束
image-20190907002631318
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
image-20190907002924866
Loading...