刚接触db,索引貌似还是一个高级货,那么多新名词,新概念让人很晕,其实索引真的很简单。我们知道IO操作是数据库访问很耗时的操作,应该尽量避免。索引就是在内存中(当然如果索引太大,也可能在硬盘固定的,连续的存储块中)建立一个真实数据的映射,通过索引,我们确定要找的数据范围,然后再通过尽量少的IO到硬盘上把目标数据抓回来。以下是可以作为索引的数据结构,其中mysql采用的是B+树。
顺序文件:几种简单的文件组织,其产生方式是将数据文件按某个查找键排序,并在该文 件上建立索引。 • 稠密索引:这种索引为数据文件的每个记录设一个键-指针对。这些键-指针对按它们的键 值顺序存放。 • 稀疏索引:这些索引为数据文件的每个存储块设一个键-指针对。与指针相对应的键为该 指针所指向的存储块中第一个键值。
• 多级索引:在索引文件上再建索引,在索引的索引上再建索引,等等,这在有时候是很有 用的。高级索引必须是稀疏的。
• 文件的扩展:随着数据文件和它的索引文件的增长,必须采取一些措施来为文件增加附加 的存储块。为文件的基本块增加溢出块是一种可行的办法。在数据文件或索引文件的块序 列表中插入更多的块,除非要求文件本身存放在连续的磁盘块中。
• 辅助索引:即使数据文件没有按查找键K排序,我们也可在键K上建立索引。这样,索引 必须是稠密的。
• 倒排索引:文件与其包含的词之间的关系通常可通过一个词-指针对的索引结构来表示。 指针指向“桶”文件的某个位置,该位置上有一个指向文件中词的出现的指针列表。
• B树:这些结构实质上是有着很好的扩充性能的多级索引。带有n个键和n+ 1个指针的存储 块被组织成一棵树。叶结点指向记录。任何时候所有索引块都在半满与全满之间。
• 范围查询:指查找键值在给定范围内的所有记录,有索引的顺序文件和B树索引可为这类 查询提供便利,但散列表索引不能。
• 散列表:同创建主存散列表一样,我们也可以基于辅存的存储块来建立散列表。散列函数 将键值映射到桶,有效地将数据文件的记录分配到多个小组(桶)。桶用一个存储块和可 能出现的溢出块表示。
• 动态索引:如果一个桶中的记录太多,势必降低散列表的性能,因而随着时间推移,桶的数 量可能需要增加。允许合理增加桶的两种重要方法是可扩展散列和线性散列。它们都首先将 键值散列到一个长位串,然后使用其中若干位来决定记录所属的桶,位的数目是可变的。
• 可扩展散列:这种方法允许在存在记录数太多的桶时将桶的数目加倍。它使用指向块的指 针数组来表示桶。为了避免块过多,几个桶可以用同一个块表示。
• 线性散列:这种方法每当桶中的记录比例超出阈值时增加一个桶。由于单个桶的记录不会 引起表的扩展,所以在某些情形下需要溢出块。
分享到:
相关推荐
由浅入深探究mysql索引结构原理、性能分析与优化
MySQL Innodb 索引原理详解
MySQL索引结构的分类 Hash索引、B+树索引、全文索引、RTree索引。 B+树索引 B+树介绍,为什么选择B+树,非聚集索引 聚集索引 第一点、第二点、第三点 不建议使用过长的字段,不建议使用非自增字段作为主键 什么条件...
Mysql-索引结构直观图解。上一篇刚刚通俗化的说明了B-TREE的几个结果与存储方式,其实跟索引感觉上还是没有关联起来, 那么本篇,就通过实际的一个数据行的例子,说明一下
Mysql索引数据结构.pptx
MySQL索引的数据结构与算法.pptx
MySQL索引 聚集索引 如果你想了解MySQL索引查询优化,你首先应该对MySQL数据组织结构、B-Tree索引、聚集索引,次要索引有一定的了解,才能够更好地理解MySQL查询优化行为。这里主要探讨MySQL InnoDB的聚集索引。
MySQL索引背后的数据结构及算法原理,技术面试重要内容呀
对Mysql(索引结构/事务/锁/MVCC/BufferPool/优化)总结,包括重要知识点与面试点,xmind源文件
讲座的一个ppt分享 1. MySQL的索引类型选择 2. MySQL数据结构分析 3. MySQL的引擎类型分析
深入理解Mysql索引底层数据结构与算法.ppt
MySQL索引背后的数据结构及算法原理,帮助了解MYsql的索引和原理,高级工程师进阶的必选。。。。。
mysql索引数据结构详解
本文档主要针对对Mysql初级爱好者进行探讨学习,欢迎更多的热爱技术、喜欢技术愿意分享技术的朋友交流。
BAT面试深入理解Mysql索引底层数据结构与算法_1
mysql 索引结构B+树与hash有何区别。分别适用于什么场景 数据库的索引还能有其他实现吗 redis跳表是如何实现的 跳表和B+树,LSM树有和区别呢 解析 首先为什么要把mysql索引和redis跳表放在一起讨论呢,因为他们...
BAT面试_深入理解Mysql索引底层数据结构与算法_4
诸葛_BAT面试_深入理解Mysql索引底层数据结构与算法_3