首页 > 技术交流 > 【有书共读】《MySQL技术内幕》读书笔记05--索引与算法

【有书共读】《MySQL技术内幕》读书笔记05--索引与算法

头像
snowbear
发布于 2018-11-09 00:17:43
回复0 | 赞 0 | 浏览227
innodb存储引擎索引分类
  1. B+树索引:平衡二叉树,二分查找法,载入数据行所在的页,然后将页读入到内存,在内存找查找所要的数据。
  2. 哈希索引:自适应,根据表的使用情况自动为表生成哈希索引
  3. 全文索引:后面将详细介绍
数据结构与算法(理解B+树,理解左旋和右旋)
  1. 二叉查找树:左子树的键值总是小于根的键值,右子树的键值大于根。中序遍历得到升序
  2. 平衡二叉树:二叉查找树,同时任意节点的左右子树高度差<=1;插入、删除和更新操作需要通过左旋和右旋来保持平衡
  3. B+树:平衡树,所有记录顺序存放在B+树的叶子节点上;叶子节点通过指针顺序链接
B+树索引

特点:高扇出性,在数据库中B+树的高度一般在2~4层.

聚集索引
  • 每张表的主键构造成一颗B+树,叶子结点中存放的事整张表的行记录数据
  • 每张表只能有一个聚集索引
  • 聚集索引的存储是逻辑上的连续

    辅助索引
  • 叶子节点不包含行记录的全部数据,由键和聚集索引构成叶子节点

  • 查找行记录:通过辅助索引找到聚集索引,在聚集索引B+树上找到行记录
  • 补充:堆表,行数据的插入顺序即为存放顺序,没有聚集索引,通过行号来查找行数据

    B+树索引分裂过程
  • InnoDB存储引擎决定是想做还是向右进行分裂

  • 确定分裂点的位置:如果插入是随机的,那么取页的中间记录为分裂点;否则定位到待插入记录的前一条记录,观察定位的记录之后是否还有3条记录,若有则分裂点为当前向后移动3条,否则分裂点为当前。
B+树索引的管理
  • 创建和删除索引:ALTER TABLE ADD/DROP和CREATE/DROP INDEX
  • 查看索引:SHOW IDNEX FROM TABLE
  • Fast Index Creation:在辅助索引的创建过程中,对数据表加上S锁,不能对表进行读操作
  • Online Schema:在事务的创建过程中,可以有读写事务对表进行操作
  • MySQL5.6以后支持Online DDL, 包括:辅助索引的创建与删除;改变自增长值;添加或删除外键约束;列重命名

    Cardinality值
  • 低选择性:某个字段的取值范围很小,没有必要使用索引

  • 通过SHOW INDEX操作查找cardinality,对选择性进行预估,索引的cardinality/rows值应该尽可能的接近1
  • 更新cardinality值:发生在INSERT和UPDATE操作,通过采样来统计cardinality值。采样过程:对8个叶子节点进行采样,叶子节点的个数为A,统计每个页中不同记录的个数Pi,cardinality=(P1+...+P8)*A/8
  • 更新策略:1.表中1/16数据发生了变化。2.stat_modified_counter>2000000000.
B+树索引的使用
联合索引
  • 对表的多个列进行索引,本质上也是一个B+树。联合索引的键也是排序的,排序左对齐
  • 优化器选择不使用索引的情况:访问的数据占整个表中数据大部分时(超过20%)
覆盖索引
  • 直接从辅助索引中查询记录,覆盖索引中不包含整行记录的所有信息
  • Explain SQL执行计划Extra列中显示Using Index
  • 一般是联合辅助索引进行统计时可以用到覆盖索引
Multi-Range Read 优化
  • 目的:减少磁盘的随机访问,将随机访问转化为较为顺序的数据访问
  • 工作方式:1.将查询到的辅助索引存入缓存;2.将缓存的数据按照RowID排序;3.按照排完序之后的顺序查找数据
Index Condition Pushdown(ICP)优化
  • MySQL会在取出索引的同时,判断是否可以进行WHERE条件的过滤,将WHERE的部分过滤操作放在了存储引擎层
哈希算法
哈希表
  • h(k),利用哈希函数h,计算关键字k的槽
  • 哈希碰撞一般采用链接法解决:将散列到同一个槽的元素放到链表中
  • 数据库一般采用除法散列:h(k) = k mod m
自适应哈希索引
  • 数据库自身创建,DBA不能干预。SHOW ENGINE INNODB STATUS查看哈希索引的使用情况
  • 哈希索引只能搜索等值的查询,范围查找不适用。
全文索引
概述
  • 将存储于数据库的整本书或整篇文章的任意内容查找出来,也可以统计和分析
  • Innodb1.2x,innodb存储引擎开始支持全文检索,支持MyISAM的全部功能。
  • 倒排索引:全文检索使用倒排索引来实现,在辅助表中存储了单词与单词自身在问的那个中位置的映射。1.inverted file index{单词,单词所在文档的ID};2.full inverted index{单词,(单词所在文档ID,在文档中的位置)}。
InnoDB全文检索
  • 使用full inverted index倒排索引,(DocumentID, Position)视为ilist,在全文检索的表中,有两列word,ilist。在word上设置索引。
  • 与MyISAM对比:全文索引中没有存放position信息
  • Auxiliary Table(辅助表):倒排索引将word存放到一张表中,持久化,存放在磁盘中。
  • FTS Index Cache(全文检索索引缓存):红黑树,根据(word,ilist)排序,InnoDB对Auxiliary Table批量更新,合并FTS。
  • innodb全文索引的限制:1.每张表只能有一个全文检索的索引。2.有多列组合而成的全文检索的索引咧必须使用相同的字符集与排序规则。3.不支持没有单词界定负的语言。
全文检索
  • Natural Language

    • 默认的全文检索模式,MATCH(col) against (expr)。
    • 相关性:word是否在文档中出现,word在文档中出现的次数,word在索引列中的数量,多上个文档包含该word。
    • stopword列中的word,不对该词查询。stopword:使用频率高,但是没有意义的单词(如a,the,at...)
  • IN BOOLEAN MODE全文检索:使用修饰符表示查询条件,+表示word必须存在,-表示必须被排除等

  • Query Expansion 全文检索的扩展查询:根据搜索的单词进行全文索引,然后根据查询出的粉刺在进行一次全文检索的查询。

0条回帖

回帖
加载中...

近期热帖

热门推荐

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-808北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号