关于mysql表索引方法btree的信息

发布时间：2023-01-08

本文目录一览：

  1. MySQL索引的Index method中btree和hash的区别
  2. MySQL BTREE索引
  3. mysql btree和hash索引对比
  4. mysql索引方法btree和hash
  5. mysql中的索引怎样使用btree索引

MySQL索引的Index method中btree和hash的区别

当分片索引不是纯整型的字符串时，只接受整型的内置 hash 算法是无法使用的。为此，stringhash 按照用户定义的起点和终点去截取分片索引字段中的部分字符，根据当中每个字符的二进制 unicode 值换算出一个长整型数值，然后就直接调用内置 hash 算法求解分片路由：先求模得到逻辑分片号，再根据逻辑分片号直接映射到物理分片。 用户需要在 rule.xml 中定义 partitionLength[] 和 partitionCount[] 两个数组和 hashSlice 二元组。 在 DBLE 的启动阶段，点乘两个数组得到模数，也是逻辑分片的数量。 并且根据两个数组的叉乘，得到各个逻辑分片到物理分片的映射表（物理分片数量由 partitionCount[] 数组的元素值之和）。 此外根据 hashSlice 二元组，约定把分片索引值中的第 4 字符到第 5 字符（字符串以 0 开始编号，编号 3 到编号 4 等于第 4 字符到第 5 字符）字符串用于 “字符串-整型”的转换。 在 DBLE 的运行过程中，用户访问使用这个算法的表时，WHERE 子句中的分片索引值会被提取出来，取当中的第 4 个字符到第 5 字符，送入下一步。 设置一个初始值为 0 的累计值，逐个取字符，把累计值乘以 31，再把这个字符的 unicode 值当成长整型加入到累计值中，如此类推直至处理完截取出来的所有字符，此时的累计值就能够代表用户的分片索引值，完成了 “字符串-整型” 的转换。 对上一步的累计值进行求模，得到逻辑分片号。 再根据逻辑分片号，查映射表，直接得到物理分片号。 与MyCat的类似分片算法对比 请点击输入图片描述 两种算法在string转化为int之后，和 hash 分区算法相同，区别也继承了 hash 算法的区别。

开发注意点

  1. 分片索引：必须是字符串。
  2. 分片索引：最大物理分片配置方法是，让 partitionCount[] 数组和等于 2880。
    例如： 
    <property name="partitionLength">1</property>
<property name="partitionCount">2880</property>
    或 
    <property name="partitionLength">1,1</property>
<property name="partitionCount">1440,1440</property>
  3. 分片索引：最小物理分片配置方法是，让 partitionCount[] 数组和等于 1。
    例如： 
    <property name="partitionLength">2880</property>
<property name="partitionCount">1</property>
  4. 分片索引：partitionLength 和 partitionCount 被当做两个逗号分隔的一维数组，它们之间的点乘必须在 [1, 2880] 范围内。
  5. 分片索引：partitionLength 和 partitionCount 的配置对顺序敏感。
    例如： 
    <property name="partitionLength">512,256</property>
<property name="partitionCount">1,2</property>
    和 
    <property name="partitionLength">256,512</property>
<property name="partitionCount">2,1</property>
    是不同的分片结果。
  6. 分片索引：分片索引字段长度小于用户指定的截取长度时，截取长度会安全减少到符合分片索引字段长度。

数据分布

  1. 分片索引字段截取越长则越有利于数据均匀分布。
  2. 分片索引字段的内容重复率越低则越有利于数据均匀分布。

运维注意点

  1. 扩容：预先过量分片，并且不改变 partitionCount 和 partitionLength 点乘结果，也不改变截取设置 hashSlice 时，可以避免数据再平衡，只需进行涉及数据的迁移。
  2. 扩容：若需要改变 partitionCount 和 partitionLength 点乘结果或改变截取设置 hashSlice 时，需要数据再平衡。
  3. 缩容：预先过量分片，并且不改变 partitionCount 和 partitionLength 点乘结果，也不改变截取设置 hashSlice 时，可以避免数据再平衡，只需进行涉及数据的迁移。
  4. 缩容：若需要改变 partitionCount 和 partitionLength 点乘结果或改变截取设置 hashSlice 时，需要数据再平衡。

配置注意点

  1. 在 rule.xml 中，可配置项为 property name="partitionLength"、property name="partitionCount" 和 property name="hashSlice"。
  2. 在 rule.xml 中配置 property name="partitionLength" 标签：
    • 内容形式为：物理分片持有的虚拟分片数[,物理分片持有的虚拟分片数,...物理分片持有的虚拟分片数]
    • 物理分片持有的虚拟分片数必须是整型，物理分片持有的虚拟分片数从左到右与同顺序的物理分片数对应，partitionLength 和 partitionCount 的点乘结果必须在 [1, 2880] 范围内。
  3. 在 rule.xml 中配置 property name="partitionCount" 标签：
    • 内容形式为：物理分片数[,物理分片数,...物理分片数]
    • 其中物理分片数必须是整型，物理分片数按从左到右的顺序与同顺序的物理分片持有的虚拟分片数对应，物理分片的编号从左到右连续递进，partitionLength 和 partitionCount 的点乘结果必须在 [1, 2880] 范围内。
  4. partitionLength 和 partitionCount 的语义是：持有 partitionLength[i] 个虚拟分片的物理分片有 partitionCount[i] 个。
    例如： 
    <property name="partitionLength">512,256</property>
<property name="partitionCount">1,2</property>
    语义是持有 512 个逻辑分片的物理分片有 1 个，紧随其后，持有 256 个逻辑分片的物理分片有 2 个。
  5. partitionLength 和 partitionCount 都对书写顺序敏感。
    例如： 
    <property name="partitionLength">512,256</property>
<property name="partitionCount">1,2</property>
    分片结果是第一个物理分片持有头512个逻辑分片，第二个物理分片持有紧接着的256个逻辑分片，第三个物理分片持有最后256个逻辑分片，相对的： 
    <property name="partitionLength">256,512</property>
<property name="partitionCount">2,1</property>
    分片结果则是第一个物理分片持有头 256 个逻辑分片，第二个物理分片持有紧接着的 256 个逻辑分片，第三个物理分片持有最后 512 个逻辑分片。
  6. partitionLength[] 的元素全部为 1 时，这时候 partitionCount 数组和等于 partitionLength 和 partitionCount 的点乘，物理分片和逻辑分片就会一一对应，该分片算法等效于直接取余。
  7. 在 rule.xml 中配置标签，从分片索引字段的第几个字符开始截取到第几个字符：
    • 若希望从首字符开始截取 k 个字符（k 为正整数），配置的内容形式可以为“0:k”、“k”或“:k”；
    • 若希望从末字符开始截取 k 个字符（k 为正整数），则配置的内容形式可以为“-k:0”、“-k”或“-k:”；
    • 若希望从头第 m 个字符起算截取 n 个字符（m 和 n 都是正整数），则先计算出 i = m - 1 和 j = i + n - 1，配置的内容形式为“i:j”；
    • 若希望从尾第 m 个字符起算截取从尾算起的 n 个字符（m 和 n 都是正整数），则先计算出 i = -m + n - 1，配置的内容形式可以为“-m:i”；
    • 若希望不截取，则配置的内容形式可以为“0:0”、“0:”、“:0”或“:”。

MySQL BTREE索引

个人能力有限，如有错误请指出，共同学习。

二叉树

B树

B+树

特点：

  • 聚簇索引
  • 二级索引

key数据存储量估算：

若每个页可以存1000个key，而且树的高度是4，那么 前提条件如下：

插入步骤

步骤一

因为索引中还没有数据，所以此时的B+树只有一个空的根结点，又由于一个页只能存3个key，首先将10，20，5插入进去（实际上此步发生了3次插入），然后在页面内做数据排序，最终结果如下图：

步骤二

由于根页面已经写满，此时插入8，将发生分裂（根页面分裂），大致步骤如下：

注意：在分裂过程中，根结点始终是不会变的，不管变成多大的树，根结点的页面号始终如一。

步骤五

插入数据40，发现比根结点23大，找到103号页面，发现已满，执行分裂，分裂同上面叶子结点的分裂步骤。分裂后如图所示：

步骤六

继续插入下一个数据9，因为比20小，找到101号页面，发现已满，需要做叶子结点分裂，如下图： 传统B+树的数据删除，一般都会有一个所谓的填充因子，来控制页面数据的删除比例，如果数据量小于这个填充因子所表示的数据量，就会有节点合并，这与分裂是相对应的。 InnoDB的实现与传统B+树算法有不同之处，InnoDB在删除索引数据时，会先检查当前页剩余的记录数，如果只剩下一条记录，就会直接将这个页面从B+树中摘除，也只有这种情况，InnoDB才会回收一个页面，但是对于根节点，即使索引数据全部删除，根节点页依然存在，只不过是以空页的形式存在。 下面举个例子描述索引删除过程，前提条件与前面插入记录时一致。

删除数据 50

删除过程全部结束，最终得到一个空的索引页。 《MySQL运维内参》 B+树动画演示：

mysql btree和hash索引对比

只有 MEMORY 存储引擎的表才可以选择使用 BTREE 索引或者 HASH 索引，像我们常用的 InnoDB 只支持 BTREE 索引。两种不同类型的索引各有其不同的适用范围。 Hash索引只能用于对等比较，例如 =, IN（相当于 =）操作符。时间复杂度是 O(1)，一次查找便能定位数据，不像 BTree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次 IO 访问，所以 Hash 在单值查询下检索效率远高于 BTree 索引。 但是，事实上我们更多情况是使用 BTree 而不是 Hash。 HASH 索引有一些重要的特征需要在使用的时候特别注意，如下所示。 下面我们可以进行验证： 创建一个 city_memory 表，其中 country_id 字段上加了 HASH 索引。 插入数据：

  1. 先看这条等值条件 SQL：
  2. 那么再来看大于和小于条件 SQL：
  3. 那么 IN 这种范围条件呢？ IN 条件对于 Hash 来说是支持的，同样 BTree 当然也支持。而且 BTree 索引在使用 IN 条件找数据时相对于 Hash 性能更好，因为 rows 由 4 变为 2（说明使用 BTree 扫描 2 行即可找到）证明如下：
  4. BETWEEN .. AND .. 条件呢？ BETWEEN .. AND .. 条件在不会用到 Hash 索引！再来看看 BTree 的情况： BETWEEN .. AND .. 条件能够使用到 BTree 索引。
  5. LIKE 条件呢？ 为了使用 LIKE 条件，我们先将 country_id 类型改为 VARCHAR。 我们再来执行： LIKE 条件会让 Hash 索引失效。我们再来看 BTree 下的 LIKE 怎样： 好的，BTree 下也支持 LIKE 的不带开头 % 的访问查询。
  6. 先来看 Hash 索引支不支持排序： Hash 索引果然不能用在排序中，这多么致命呀！产生了 Using filesort 文件内排序。性能上是个大坑。
  7. 同样，我们知道分组是要基于排序的。排序不使用索引，分组当然也不使用索引了。验证如下： 最终不仅没使用到索引，还产生了文件内排序和使用临时表。 当使用 MEMORY 引擎表的时候，如果是默认创建的 HASH 索引，就要注意 SQL 语句的编写，确保可以使用上索引，如果索引字段需要范围查询、排序、分组就请使用 BTree 索引。

mysql索引方法btree和hash

Hash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像 B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的 IO 访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。 可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢？任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些。

  1. Hash 索引仅仅能满足 =, IN 和 <> 查询，不能使用范围查询。 由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和 Hash 运算前完全一样。
  2. Hash 索引无法被用来避免数据的排序操作。 由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且 Hash 值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算。
  3. Hash 索引不能利用部分索引键查询。 对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。
  4. Hash 索引在任何时候都不能避免表扫描。 前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash 运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
  5. Hash 索引遇到大量 Hash 值相等的情况后性能并不一定就会比 B-Tree 索引高。 对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

mysql中的索引怎样使用btree索引

B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型，除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL 中是如此，实际上在其他的很多数据库管理系统中 B-Tree 索引也同样是作为最主要的索引类型，这主要是因为 B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。 一般来说，MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的，也就是所有实际需要的数据都存放于 Tree 的 Leaf Node，而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的，所以我们大家都称之为 B-Tree 索引。当然，可能各种数据库（或 MySQL 的各种存储引擎）在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 InnoDB 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree，也就是在 B-Tree 数据结构的基础上做了很小的改造，在每一个 Leaf Node 上面除了存放索引键的相关信息之外，还存储了指向与该 Leaf Node 相邻的后一个 Leaf Node 的指针信息，这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。 在 InnoDB 存储引擎中，存在两种不同形式的索引，一种是 Cluster 形式的主键索引（Primary Key），另外一种则是和其他存储引擎（如 MyISAM 存储引擎）存放形式基本相同的普通 B-Tree 索引，这种索引在 InnoDB 存储引擎中被称为 Secondary Index。

推荐文章