精华内容
下载资源
问答
  • 这里讲述 MySQL 哈希索引的实现方式以及使用场景。 哈希表在 MySQL 里有如下应用: 各种存储引擎的哈希索引存储。MySQL 的 Memory,NDB 都有哈希索引的具体实现; MySQL 内部生成的哈希表。比如: 数据在 innodb ...

    这里讲述 MySQL 哈希索引的实现方式以及使用场景。
    哈希表在 MySQL 里有如下应用:

    1. 各种存储引擎的哈希索引存储。MySQL 的 Memory,NDB 都有哈希索引的具体实现;
    2. MySQL 内部生成的哈希表。比如:
    • 数据在 innodb buffer pool 里的快速查找;
    • 子查询的物化自动加哈希索引;
    • JOIN KEY 无 INDEX 下的 HASH JOIN 等。

    一、哈希数据分布

    哈希索引显式应用主要存在于内存表,也就是 Memory 引擎,或者是 MySQL 8.0 的 Temptable 引擎。本篇的内容上都是基于内存表,MySQL 内存表的大小由参数 max_heap_table_size 来控制,其中包含了表数据,索引数据等。

    举个例子,表 t1 有六行记录,主键哈希索引。

    # MySQL 内存表主键默认哈希索引
    mysql> create table t1(id int , name varchar(64), gender char(1), status char(2),primary key (id)) engine memory;
    Query OK, 0 rows affected (0.02 sec)
    
    mysql> insert into t1 values(101,'张三','男','未婚');
    Query OK, 1 row affected (0.00 sec)
    
    mysql> insert into t1 values(102,'小明','男','已婚');
    Query OK, 1 row affected (0.01 sec)
    
    mysql> insert into t1 values(103,'李四','男','未婚');
    Query OK, 1 row affected (0.01 sec)
    
    mysql> insert into t1 values(104,'李庆','女','已婚');
    Query OK, 1 row affected (0.00 sec)
    
    mysql> insert into t1 values(105,'杨阳','女','未婚');
    Query OK, 1 row affected (0.01 sec)
    
    mysql> insert into t1 values(106,'余欢水','男','二婚');
    Query OK, 1 row affected (0.01 sec)
    

    我简单画了张主键哈希索引的分布图,见图 1:

    图 1 展示了 MySQL 内存表的哈希主键分布。MySQL 内存表允许非主键哈希索引存在。假设给列 name 加一个哈希索引,

    mysql> alter table t1 add key idx_name(name) using hash;
    Query OK, 6 rows affected (0.04 sec)
    Records: 6  Duplicates: 0  Warnings: 0
    
    mysql> insert into t1 values(107,'杨阳','男','二婚');
    Query OK, 1 row affected (0.00 sec)
    

    此时基于 name 列的哈希索引如图 2:

    由图 2 发现,name 列做索引存在一定几率的哈希值碰撞,这类碰撞越多,哈希索引的性能下降越快,所以这种场景反而发挥不到哈希索引的优势。

    二、使用场景

    接下来我们来看看在 MySQL 哈希索引的使用场景。为了对比 B 树索引,建一张表 t1 的克隆表 t2。

    # 省略表 t1 造数据过程
    mysql> create table t2 like t1;
    Query OK, 0 rows affected (0.02 sec)
    
    mysql> alter table t2 drop primary key, drop key idx_name;
    Query OK, 0 rows affected (0.04 sec)
    Records: 0  Duplicates: 0  Warnings: 0
    
    mysql> alter table t2 add primary key (id) using btree, add key idx_name (name) using btree;
    Query OK, 0 rows affected (0.04 sec)
    Records: 0  Duplicates: 0  Warnings: 0
    
    mysql> insert into t2 select * from t1;
    Query OK, 50000 rows affected (0.18 sec)
    Records: 50000  Duplicates: 0  Warnings: 0
    

    2.1 哈希索引非常适合等值查找

    仅限于以下操作符:"=",“in”,"<=>"

    “=” 和 “in” 大家都很熟悉,简单说下 “<=>”, “<=>” 也是等值操作符,不同的是可以比较 NULL 值,操作符左右两边都为 NULL 返回 1;任意一边非 NULL,返回 0;两边都非 NULL 也返回 1。见以下 SQL 0。

    # SQL 0
    mysql> select 10<=>10,null<=>null,null<=>true;
    +---------+-------------+-------------+
    | 10<=>10 | null<=>null | null<=>true |
    +---------+-------------+-------------+
    |       1 |           1 |           0 |
    +---------+-------------+-------------+
    1 row in set (0.00 sec)
    

    接下来的几个 SQL 都是基于操作 “=” 和 “in”。

    # SQL 1
    mysql> select * from t1 where id = 2000;
    +------+-----------+--------+--------+
    | id   | name      | gender | status |
    +------+-----------+--------+--------+
    | 2000 | 王牡丹    | 男     | 离异   |
    +------+-----------+--------+--------+
    1 row in set (0.00 sec)
    

    SQL 1 为基于主键的等值查询,非常适合用哈希索引,计算列 id=2000 的哈希值,能快速通过索引找到对应的记录。

    # SQL 2
    mysql> select * from t2 where id in (1000,2000);
    +------+-----------+--------+--------+
    | id   | name      | gender | status |
    +------+-----------+--------+--------+
    | 1000 | 余欢水    | 男     | 二婚   |
    | 2000 | 王牡丹    | 男     | 离异   |
    +------+-----------+--------+--------+
    2 rows in set (0.00 sec)
    

    SQL 2 虽然为 IN,但是子串的条件非常稀少(只有两个),也适合用哈希索引。

    # SQL 3 
    mysql> select count(*) from t1 where id between 1000 and 2000;
    +----------+
    | count(*) |
    +----------+
    |     1001 |
    +----------+
    1 row in set (0.02 sec)
    

    SQL 3 基于一个范围的查询,和以上两条 SQL 不一样,这种 SQL 没法走哈希索引。原因很明确:基于索引字段生成的哈希值和索引字段本身的可排序性没有任何联系,哈希索引无从下手。这样的场景,就得使用先天优势的 B 树索引。

    把 SQL 3 的表改为 t2,基于 B 树索引。

    # SQL 4
    mysql> select count(*) from t2 where id between 1000 and 2000;
    +----------+
    | count(*) |
    +----------+
    |     1001 |
    +----------+
    1 row in set (0.00 sec)
    

    对比下 SQL 3 和 SQL 4 的执行计划,SQL 3 不走索引,全表扫描 5W 行;SQL4 走主键索引只扫描 3000 行。

    mysql> explain select count(*) from t1 where id between 1000 and 2000\G
    *************************** 1. row ***************************
              id: 1
     select_type: SIMPLE
           table: t1
      partitions: NULL
            type: ALL
    possible_keys: PRIMARY
             key: NULL
         key_len: NULL
             ref: NULL
            rows: 50000
        filtered: 11.11
           Extra: Using where
    1 row in set, 1 warning (0.00 sec)
    
    mysql> explain select count(*) from t2 where id between 1000 and 2000\G
    *************************** 1. row ***************************
              id: 1
     select_type: SIMPLE
           table: t2
      partitions: NULL
            type: range
    possible_keys: PRIMARY
             key: PRIMARY
         key_len: 4
             ref: NULL
            rows: 3052
        filtered: 100.00
           Extra: Using where
    1 row in set, 1 warning (0.00 sec)
    

    2.2 无法通过哈希索引排序

    哈希索引本身是无序的,所以基于哈希索引的排序只能走全表扫描,并且额外排序。SQL 5 和 SQL 6 分别对表 t1,t2 执行同样的倒序输出。

    # SQL 5
    mysql> select id from t1 where 1 order by id desc limit 1;
    +--------+
    | id     |
    +--------+
    | 135107 |
    +--------+
    1 row in set (0.02 sec)
    
    # SQL 6
    mysql> select id from t2 where 1 order by id desc limit 1;
    +--------+
    | id     |
    +--------+
    | 135107 |
    +--------+
    1 row in set (0.00 sec)
    

    来看下这两条 SQL 的执行计划:

    mysql> explain select id from t1 where 1 order by id desc limit 1\G
    *************************** 1. row ***************************
              id: 1
     select_type: SIMPLE
           table: t1
      partitions: NULL
            type: ALL
    possible_keys: NULL
             key: NULL
         key_len: NULL
             ref: NULL
            rows: 50000
        filtered: 100.00
           Extra: Using filesort
    1 row in set, 1 warning (0.00 sec)
    
    mysql> explain select id from t2 where 1 order by id desc limit 1\G
    *************************** 1. row ***************************
              id: 1
     select_type: SIMPLE
           table: t2
      partitions: NULL
            type: index
    possible_keys: NULL
             key: PRIMARY
         key_len: 4
             ref: NULL
            rows: 1
        filtered: 100.00
           Extra: Backward index scan
    1 row in set, 1 warning (0.00 sec)
    

    可以看到 SQL 6 走 B 树索引反向扫描拿回对应的 ID,SQL 5 就只能全表排序拿数据。

    2.3 哈希索引不存在 covering index 概念

    同样,由于哈希值是基于哈希函数生成,索引值并不包含数据本身,任何对哈希索引的查找都得回表。

    mysql> flush status;
    Query OK, 0 rows affected (0.01 sec)
    
    # SQL 7
    mysql> select id from t1 limit 1;
    +-----+
    | id  |
    +-----+
    | 949 |
    +-----+
    1 row in set (0.00 sec)
    
    mysql> show status like 'handler%';
    +----------------------------+-------+
    | Variable_name              | Value |
    +----------------------------+-------+
    | Handler_commit             | 0     |
    | Handler_delete             | 0     |
    | Handler_discover           | 0     |
    | Handler_external_lock      | 2     |
    | Handler_mrr_init           | 0     |
    | Handler_prepare            | 0     |
    | Handler_read_first         | 0     |
    | Handler_read_key           | 0     |
    | Handler_read_last          | 0     |
    | Handler_read_next          | 0     |
    | Handler_read_prev          | 0     |
    | Handler_read_rnd           | 0     |
    | Handler_read_rnd_next      | 849   |
    | Handler_rollback           | 0     |
    | Handler_savepoint          | 0     |
    | Handler_savepoint_rollback | 0     |
    | Handler_update             | 0     |
    | Handler_write              | 0     |
    +----------------------------+-------+
    18 rows in set (0.00 sec)
    
    mysql> flush status;
    Query OK, 0 rows affected (0.01 sec)
    
    # SQL 8
    mysql> select id from t2 limit 1;
    +-----+
    | id  |
    +-----+
    | 949 |
    +-----+
    1 row in set (0.00 sec)
    
    mysql> show status like 'handler%';
    +----------------------------+-------+
    | Variable_name              | Value |
    +----------------------------+-------+
    | Handler_commit             | 0     |
    | Handler_delete             | 0     |
    | Handler_discover           | 0     |
    | Handler_external_lock      | 2     |
    | Handler_mrr_init           | 0     |
    | Handler_prepare            | 0     |
    | Handler_read_first         | 0     |
    | Handler_read_key           | 0     |
    | Handler_read_last          | 0     |
    | Handler_read_next          | 0     |
    | Handler_read_prev          | 0     |
    | Handler_read_rnd           | 0     |
    | Handler_read_rnd_next      | 1     |
    | Handler_rollback           | 0     |
    | Handler_savepoint          | 0     |
    | Handler_savepoint_rollback | 0     |
    | Handler_update             | 0     |
    | Handler_write              | 0     |
    +----------------------------+-------+
    18 rows in set (0.00 sec)
    

    以上分别执行 SQL 7 和 SQL 8 。两条 SQL 只拿出索引键,对比下 MySQL 的 HANDLER 状态,发现 SQL 7 回表了 849 次才找到记录;SQL 8 只回表了一次。

    2.4 哈希索引不同于B+树,不能基于部分索引查询

    比如对字段 (x1,x2,x3) 建立联合哈希索引,由于哈希值是针对这三个字段联合计算,只有一个,不能针对单个字段来走索引。在此基础上,在建立上两表,主键为联合索引,表 t3 主键是哈希索引,表 t4 主键是 B 树索引。

    mysql> create table t3(id1 int,id2 int,r1 int, primary key(id1,id2)) engine memory;
    Query OK, 0 rows affected (0.03 sec)
    
    mysql> create table t4(id1 int,id2 int,r1 int, primary key(id1,id2) using btree) engine memory;
    Query OK, 0 rows affected (0.03 sec)
    
    #省略造数据过程。
    mysql> select (select count(*) from t3) t3, (select count(*) from t4) t4;
    +-------+-------+
    | t3    | t4    |
    +-------+-------+
    | 16293 | 16293 |
    +-------+-------+
    1 row in set (0.00 sec)
    
    # SQL 9
    mysql> select * from t3 where id1 = 44;
    +-----+-----+------+
    | id1 | id2 | r1   |
    +-----+-----+------+
    |  44 |  98 |   29 |
    |  44 | 180 |   56 |
    |  44 | 130 |   32 |
    |  44 | 104 |   65 |
    |  44 | 208 |    4 |
    |  44 | 154 |  113 |
    |  44 |  69 |   84 |
    |  44 |  76 |  154 |
    |  44 | 132 |   33 |
    |  44 | 108 |   79 |
    |  44 | 173 |    6 |
    +-----+-----+------+
    11 rows in set (0.00 sec)
    
    # SQL 10
    mysql> select * from t4 where id1 = 44;
    +-----+-----+------+
    | id1 | id2 | r1   |
    +-----+-----+------+
    |  44 |  69 |   84 |
    |  44 |  76 |  154 |
    |  44 |  98 |   29 |
    |  44 | 104 |   65 |
    |  44 | 108 |   79 |
    |  44 | 130 |   32 |
    |  44 | 132 |   33 |
    |  44 | 154 |  113 |
    |  44 | 173 |    6 |
    |  44 | 180 |   56 |
    |  44 | 208 |    4 |
    +-----+-----+------+
    11 rows in set (0.00 sec)
    

    SQL 9 和 SQL 10 都是基于联合主键第一个字段查询。简单看下执行计划。很明显,SQL 9 没走索引,SQL10 走主键。

    mysql> explain select * from t3 where id1 = 44\G
    *************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: t3
       partitions: NULL
             type: ALL
    possible_keys: PRIMARY
              key: NULL
          key_len: NULL
              ref: NULL
             rows: 16293
         filtered: 10.00
            Extra: Using where
    1 row in set, 1 warning (0.00 sec)
    
    mysql> explain select * from t4 where id1 = 44\G
    *************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: t4
       partitions: NULL
             type: ref
    possible_keys: PRIMARY
              key: PRIMARY
          key_len: 4
              ref: const
             rows: 30
         filtered: 100.00
            Extra: NULL
    1 row in set, 1 warning (0.00 sec)
    

    这篇关于 MySQL 哈希索引的介绍就到此为止。这篇主要讲 MySQL 哈希索引的数据分布以及使用场景,希望对大家有帮助。


    关于 MySQL 的技术内容,你们还有什么想知道的吗?赶紧留言告诉小编吧!

    展开全文
  • MySQL索引之哈希索引和自适应哈希索引(Adaptive Hash Index) 官网:https://dev.mysql.com/doc/refman/...
    MySQL索引之哈希索引和自适应哈希索引(Adaptive Hash Index)



     官网:https://dev.mysql.com/doc/refman/5.6/en/innodb-adaptive-hash.html





    索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。


    从MySQL逻辑架构来看,MySQL有三层架构,第一层连接,第二层查询解析、分析、优化、视图、缓存,第三层,存储引擎。

    MySQL逻辑架构

    索引通过分开查询片,节省了扫描查找时间,大大提升查询效率。

    大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构。

    索引主要在存储引擎层上,不同的引擎也就有不同的B-Tree算法。




    0x01.Hash Index

    哈希索引只有Memory, NDB两种引擎支持,Memory引擎默认支持哈希索引,如果多个hash值相同,出现哈希碰撞,那么索引以链表方式存储。

    但是,Memory引擎表只对能够适合机器的内存切实有限的数据集。

    要使InnoDB或MyISAM支持哈希索引,可以通过伪哈希索引来实现,叫自适应哈希索引。

    主要通过增加一个字段,存储hash值,将hash值建立索引,在插入和更新的时候,建立触发器,自动添加计算后的hash到表里。

    直接索引

    假如有一个非常非常大的表,如下:


    CREATE TABLE IF NOT EXISTS `User` (
      `id` int(10) NOT NULL COMMENT '自增id',
      `name` varchar(128) NOT NULL DEFAULT '' COMMENT '用户名',
      `email` varchar(128) NOT NULL DEFAULT '' COMMENT '用户邮箱',
      `pass` varchar(64) NOT NULL DEFAULT '' COMMENT '用户密码',
      `last` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '最后登录时间'
    ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

    这个时候,比如说,用户登陆,我需要通过email检索出用户,通过explain得到如下:

    mysql> explain SELECT id FROM User WHERE email = ‘ooxx@gmail.com’ LIMIT 1;

    +----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
    | id | select_type | table | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
    +----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
    |  1 | SIMPLE      | User  | ALL  | NULL          | NULL | NULL    | NULL | 384742 | Using where |
    +----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
    
    


    发现 rows = 384742 也就是要在384742里面进行比对email这个字段的字符串。

    这条记录运行的时间是:Query took 0.1744 seconds,数据库的大小是40万。

    从上面可以说明,如果直接在email上面建立索引,除了索引区间匹配,还要进行字符串匹配比对,email短还好,如果长的话这个查询代价就比较大。

    如果这个时候,在email上建立哈希索引,查询以int查询,性能就比字符串比对查询快多了。

    Hash 算法

    建立哈希索引,先选定哈希算法,这里选用CRC32。

    《高性能MySQL》说到的方法CRC32算法,建立SHA或MD5算法是划算的,本身位数都有可能比email段长了。

    INSERT UPDATE SELECT 操作

    在表中添加hash值的字段:

    mysql> ALTER TABLE User ADD COLUMN email_hash int unsigned NOT NULL DEFAULT 0;

    接下来就是在UPDATE和INSERT的时候,自动更新 email_hash 字段,通过MySQL触发器实现:

    DELIMITER |
    CREATE TRIGGER user_hash_insert BEFORE INSERT ON `User` FOR EACH ROW BEGIN
    SET NEW.email_hash=crc32(NEW.email);
    END;
    |
    CREATE TRIGGER user_hash_update BEFORE UPDATE ON `User` FOR EACH ROW BEGIN
    SET NEW.email_hash=crc32(NEW.email);
    END;
    |
    DELIMITER ;



    这样的话,我们的SELECT请求就会变成这样:

    mysql> SELECT emailemail_hash FROM User WHERE email_hash = CRC32(“F2dgTSWRBXSZ1d3O@gmail.com”) ANDemail = “F2dgTSWRBXSZ1d3O@gmail.com”;


    +----------------------------+------------+
    | email                      | email_hash |
    +----------------------------+------------+
    | F2dgTSWRBXSZ1d3O@gmail.com | 2765311122 |
    +----------------------------+------------+

    在没建立hash索引时候,请求时间是 0.2374 seconds,建立完索引后,请求时间直接变成 0.0003 seconds。

    AND email = "F2dgTSWRBXSZ1d3O@gmail.com" 是为了防止哈希碰撞导致数据不准确。




    0x02.Hash Index 缺点

    哈希索引也有几个缺点:

    • 索引存放的是hash值,所以仅支持 < = > 以及 IN 操作
    • hash索引无法通过操作索引来排序,因为存放的时候经过hash计算,但是计算的hash值和存放的不一定相等,所以无法排序
    • 不能避免全表扫描,只是由于在memory表里支持非唯一值hash索引,就是不同的索引键,可能存在相同的hash值
    • 如果哈希碰撞很多的话,性能也会变得很差
    • 哈希索引无法被用来避免数据的排序操作




    警惕 InnoDB 和 MyISAM 创建 Hash 索引陷阱

    MySql 最常用存储引擎 InnoDB 和 MyISAM 都不支持 Hash 索引,它们默认的索引都是 B-Tree。但是如果你在创建索引的时候定义其类型为 Hash,MySql 并不会报错,而且你通过 SHOW CREATE TABLE 查看该索引也是 Hash,只不过该索引实际上还是 B-Tree。
    比如表 data_dict 的 DDL:
    [sql]   view plain  copy
     print ?
    1. CREATE TABLE `data_dict` (  
    2.   `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',  
    3.   `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',  
    4.   `data_name` varchar(64) NOT NULL COMMENT '数据字典值',  
    5.   PRIMARY KEY (`data_type`,`data_code`)  
    6. ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='数据字典表';  

    我们为 data_name 字段建立 Hash 索引:
    [sql]   view plain  copy
     print ?
    1. ALTER TABLE data_dict ADD INDEX data_dict_dn USING HASH (data_name);  

    打印结果:
    受影响的行: 0
    时间: 0.345s

    然后查看建表 DDL:
    [sql]   view plain  copy
     print ?
    1. SHOW CREATE TABLE data_dict;  

    打印结果:
    CREATE TABLE `data_dict` (
      `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',
      `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',
      `data_name` varchar(64) NOT NULL COMMENT '数据字典值',
      PRIMARY KEY (`data_type`,`data_code`),
      KEY `data_dict_dn` (`data_name`) USING HASH
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='数据字典表'

    是 Hash,所以我们以为创建 Hash 索引成功。
    事实上并非如此,我们都被 MySql 给骗了,我们使用 SHOW INDEXES FROM 语句对该表索引进行检索:
    [sql]   view plain  copy
     print ?
    1. SHOW INDEXES FROM data_dict;  

    打印结果:
    我们使用 SHOW INDEXES FROM 语句对该表索引进行检索
    打回原形了。不过也不要失望,虽然常见存储引擎并不支持 Hash 索引,但 InnoDB 有另一种实现方法:自适应哈希索引。InnoDB 存储引擎会监控对表上索引的查找,如果观察到建立哈希索引可以带来速度的提升,则建立哈希索引。
    我们可以通过 SHOW ENGINE INNODB STATUS 来查看当前自适应哈希索引的使用状况:
    =====================================
    2015-07-07 10:51:19 1d68 INNODB MONITOR OUTPUT
    =====================================
    Per second averages calculated from the last 36 seconds
    ......
    -------------------------------------
    INSERT BUFFER AND ADAPTIVE HASH INDEX
    -------------------------------------
    Ibuf: size 1, free list len 2633, seg size 2635, 0 merges
    merged operations:
     insert 0, delete mark 0, delete 0
    discarded operations:
     insert 0, delete mark 0, delete 0
    Hash table size 348731, node heap has 2 buffer(s)
    0.00 hash searches/s, 0.00 non-hash searches/s
    ......

    从中我们可以看到自适应哈希索引的相关信息:有使用大小、使用情况、每秒使用自适应哈希索引搜索的情况等。
    MySql 各种存储引擎的特性对比详单:
    MySql 各种存储引擎的特性对比详单
    从中我们可以看出,
    • InnoDB 支持事务,支持行级别锁定,支持 B-tree、Full-text 等索引,不支持 Hash 索引;
    • MyISAM 不支持事务,支持表级别锁定,支持 B-tree、Full-text 等索引,不支持 Hash 索引;
    • Memory 不支持事务,支持表级别锁定,支持 B-tree、Hash 等索引,不支持 Full-text 索引;
    • NDB 支持事务,支持行级别锁定,支持 Hash 索引,不支持 B-tree、Full-text 等索引;
    • Archive 不支持事务,支持表级别锁定,不支持 B-tree、Hash、Full-text 等索引;
    可以使用 SHOW ENGINES 语句查看你的 MySql Server 所支持的存储引擎,比如笔者用于本机测试的 5.6.25-log Win 版的查看结果如下:
    支持的存储引擎

    从中可以看出,InnoDB 是该版本 MySql 的默认存储引擎,也只有 InnoDB 能够支持事务、行级别锁定、外键;支持的 MEMORY 是基于哈希的,数据都存放于内存,适用于临时表。没有看到既支持事务又支持哈希索引的 NDB 的身影。

    为印证默认的存储引擎,我们创建一个测试表 data_dict_test,注意建表语句里没有定义存储引擎:


    [sql]   view plain  copy
     print ?
    1. CREATE TABLE `data_dict_test` (  
    2.   `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',  
    3.   `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',  
    4.   `data_name` varchar(64) NOT NULL COMMENT '数据字典值',  
    5.   PRIMARY KEY (`data_type`,`data_code`)  
    6. DEFAULT CHARSET=utf8 COMMENT='数据字典表';  
    打印结果:


    [SQL] CREATE TABLE `data_dict_test` (
      `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',
      `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',
      `data_name` varchar(64) NOT NULL COMMENT '数据字典值',
      PRIMARY KEY (`data_type`,`data_code`)
    ) DEFAULT CHARSET=utf8 COMMENT='数据字典表';
    受影响的行: 0
    时间: 0.262s

    然后查看建表 DDL:


    [sql]   view plain  copy
     print ?
    1. SHOW CREATE TABLE data_dict_test;  
    打印结果:


    CREATE TABLE `data_dict_test` (
      `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',
      `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',
      `data_name` varchar(64) NOT NULL COMMENT '数据字典值',
      PRIMARY KEY (`data_type`,`data_code`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='数据字典表'

    这次 SHOW CREATE TABLE 没有欺骗我们,明确给出的就是 InnoDB,虽然我们建表时没有指定。

    笔者建议使用 SHOW TABLE STATUS 语句来查看特定表的存储引擎:


    [sql]   view plain  copy
     print ?
    1. SHOW TABLE STATUS WHERE NAME = 'data_dict_test';  
    打印结果:


    SHOW TABLE STATUS WHERE NAME = 'data_dict_test'


    参考资料



    btree索引:

    如果没有特别指明类型,多半说的就是btree索引,它使用btree数据结构来存储数据,大多数mysql引擎都支持这种索引,archive引擎是一个例外5.1之前这个引擎不支持任何索引,5.1开始才支持单列自增的索引。innodb使用b+tree=btree(btree已经不使用了)

    存储引擎以不同的方式使用btree索引,性能也各不相同,各有优劣,如:myisam使用前缀压缩技术使得索引更小(但也可能导致连接表查询性能降低),但innodb则按照原数据格式进行存储,再如:myisam索引通过数据的物理位置来引用被索引的行,而innodb则根据主键来引用被索引的行。

    btree通常意味着所有的值都是按照顺序存储的,并且每一个叶子页到根的距离相同

    ,下图是innodb索引工作示意图,myisam使用的结构有所不同,但基本思想类似:

                                                                      图片来源于高性能mysql第三版

    btree索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取需要的数据,取而代之的是从索引的根节点开始进行搜索,根节点的槽中存放了指向子节点的指针,存储引擎根据这些指针向下层查找,通过比较节点页的值和要查找的值可以找到合适的指针进入下一层子节点,这些指针实际上定义了子节点页中值的上限和下限,最终存储引擎要么是找到对应的值,要么是该记录不存在。

    叶子节点比较特别,他们的指针指向的是被索引的数据,而不是其他的节点页(不同的引擎指针类型不同),其实在根节点与叶子节点之间可能有很多层节点页,树的深度和表的大小直接相关。

     

    btree树索引列是顺序组织存储的,所以很适合查找范围数据,

    有表:

    create table people(last_name varchar(50) not null,first_name varchar(50) not null,dob date not null,gender enum(‘m’,’f’) not null,key(last_name,first_name,dob));

     

    对于表中的每一行数据,索引中包含了last_name,first_name,dob列的值,下图显示了该索引是如何组织数据的存储的:

                                                             图片来源于高性能mysql第三版

    注意:索引对多个值进行排序的依据是create table语句中定义索引时的列顺序,上图中,最后两个值的姓名都一样时,就按照出生日期来排序了。

     

    可以使用btree索引的查询类型,btree索引使用用于全键值、键值范围、或者键前缀查找,其中键前缀查找只适合用于根据最左前缀的查找。前面示例中创建的多列索引对如下类型的查询有效:

    A:全值匹配

    全值匹配指的是和索引中的所有列进行匹配,即可用于查找姓名和出生日期

    B:匹配最左前缀

    如:只查找姓,即只使用索引的第一列

    C:匹配列前缀

    也可以只匹配某一列值的开头部分,如:匹配以J开头的姓的人,这里也只是使用了索引的第一列,且是第一列的一部分

    D:匹配范围值

    如查找姓在allen和barrymore之间的人,这里也只使用了索引的第一列

    E:精确匹配某一列并范围匹配另外一列

    如查找所有姓为allen,并且名字字母是K开头的,即,第一列last_name精确匹配,第二列first_name范围匹配

    F:只访问索引的查询

    btree通常可以支持只访问索引的查询,即查询只需要访问索引,而无需访问数据行,即,这个就是覆盖索引的概念。需要访问的数据直接从索引中取得。

     

    因为索引树中的节点是有序的,所以除了按值查找之外,索引还可以用于查询中的order by操作,一般来说,如果btree可以按照某种方式查找的值,那么也可以按照这种方式用于排序,所以,如果order by子句满足前面列出的几种查询类型,则这个索引也可以满足对应的排序需求。

     

    下面是关于btree索引的限制:

    A:如果不是按照索引的最左列开始查找的,则无法使用索引(注意,这里不是指的where条件的顺序,即where条件中,不管条件顺序,只要where中出现的列在多列索引中能够从最左开始连贯起来就能使用到多列索引)

    B:不能跳过索引中的列,如:查询条件为姓和出生日期,跳过了名字列,这样,多列索引就只能使用到姓这一列

    C:如果查询中有某个列的范围查询,则其右边所有列都无法使用索引优化查询,如:where last_name=xxx and first_name like ‘xxx%’ and dob=’xxx’;这样,first_name列可以使用索引,这列之后的dob列无法使用索引。

     

    哈希索引:

    基于哈希表实现,只有精确匹配索引所有列的查询才有效,对于每一行数据,存储引擎都会对所有的索引列的值计算一个哈希码,哈希码是一个较小的值,并且不同键值的行计算出来的哈希码不一样,哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。

     

    mysql中,只有memory引擎显式支持哈希索引,这也是memory引擎表的默认索引类型,memory也支持btree,值得一提的是,memory引擎是支持非唯一哈希索引的。在数据库世界里是比较与众不同,如果多个列的哈希值相同,索引会以链表的方式存放多个记录指针到同一个哈希条目中。

    示例:

    mysql> create table testhash(fname varchar(50) not null,lname varchar(50) not null,key using hash(fname)) engine=memory;
    Query OK, 0 rows affected (0.01 sec)
     
    mysql> insert into testhash values('Arjen','Lentz'),('Baron','Schwartz'),('Peter','Zaitsev'),('Vadim','Tkachenko');
    Query OK, 4 rows affected (0.00 sec)
    Records: 4  Duplicates: 0  Warnings: 0
     
    mysql> select * from testhash;
    +-------+-----------+
    | fname | lname     |
    +-------+-----------+
    | Arjen | Lentz     |
    | Baron | Schwartz  |
    | Peter | Zaitsev   |
    | Vadim | Tkachenko |
    +-------+-----------+
    4 rows in set (0.00 sec)
     
    假设索引使用假想的哈希函数f(),它返回下面的值:
    f('Arjen')=2323
    f('Baron')=7437
    f('Peter')=8784
    f('Vadim')=2458
     
    则哈希索引的数据结构如下:
    槽:        值:
    2323        指向第1行的指针
    2458        指向第4行的指针
    7437        指向第2行的指针
    8784        指向第3行的指针

      

    每个槽的编号是顺序的,但是数据行不是顺序的。下面来看一句查询:

    select lname from testhash where fname='Peter';

      

    mysql先计算Peter的哈希值,并使用该值寻找对应的记录指针,因为f(‘Peter’)=8784,所以mysql在索引中查找8784,可以找到指向第三行的指针,最后一步是比较第三行的值是否为Peter,以确保就是要查找的行。因为索引自身只需要存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快,然而,哈希索引也有限制,如下:

     

    A:哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行(即不能使用哈希索引来做覆盖索引扫描),不过,访问内存中的行的速度很快(因为memory引擎的数据都保存在内存里),所以大部分情况下这一点对性能的影响并不明显。

    B:哈希索引数据并不是按照索引列的值顺序存储的,所以也就无法用于排序

    C:哈希索引也不支持部分索引列匹配查找,因为哈希索引始终是使用索引的全部列值内容来计算哈希值的。如:数据列(a,b)上建立哈希索引,如果只查询数据列a,则无法使用该索引。

    D:哈希索引只支持等值比较查询,如:=,in(),<=>(注意,<>和<=>是不同的操作),不支持任何范围查询(必须给定具体的where条件值来计算hash值,所以不支持范围查询)。

    E:访问哈希索引的数据非常快,除非有很多哈希冲突,当出现哈希冲突的时候,存储引擎必须遍历链表中所有的行指针,逐行进行比较,直到找到所有符合条件的行。

    F:如果哈希冲突很多的话,一些索引维护操作的代价也很高,如:如果在某个选择性很低的列上建立哈希索引(即很多重复值的列),那么当从表中删除一行时,存储引擎需要遍历对应哈希值的链表中的每一行,找到并删除对应的引用,冲突越多,代价越大。

     

    从上面描述可知,哈希索引只适合某些特定的场景,而一旦适合哈希索引,则它带来的性能提升非常明显,除了memory引擎外,NDB引擎也支持唯一哈希索引,且NDB存储引擎中作用非常特殊,但这里不讨论。

     

    innodb引擎有一个特殊的功能叫做自适应哈希索引,当innodb注意到某些索引值被使用的非常频繁时,它会在内存中基于btree索引之上再创建一个哈希索引,这样就让btree索引也具有哈希索引的一些优点,比如:快速的哈希查找,这是一个全自动的,内部的行为,用户无法控制或者配置,不过如果有必要,可以选择关闭这个功能(innodb_adaptive_hash_index=OFF,默认为ON)。

     



    自适应哈希索引采用之前讨论的哈希表的方式实现,不同的是,这仅是数据库自身创建并使用的,DBA本身并不能对其进行干预。自适应哈希索引近哈希函数映射到一个哈希表中,因此对于字典类型的查找非常快速,如SELECT * FROM TABLE WHERE index_col='xxx'但是对于范围查找就无能为力。通过SHOW ENGINE INNODB STATUS 可以看到当前自适应哈希索引的使用情况

    -------------------------------------
    INSERT BUFFER AND ADAPTIVE HASH INDEX
    -------------------------------------
    Ibuf: size 1, free list len 0, seg size 2, 94 merges
    merged operations:
     insert 280, delete mark 0, delete 0
    discarded operations:
     insert 0, delete mark 0, delete 0
    Hash table size 4425293, node heap has 1337 buffer(s)
    174.24 hash searches/s, 169.49 non-hash searches/s

    现在可以看到自适应哈希索引的使用信息了。包括自适应哈希索引的大小、使用情况,每秒使用自适应哈希索引搜索的情况。需要注意的是,哈希索引只能用来搜索等值的查询,如

    SELECT * FROM table WHERE index_col='xxx'

    而对于其他查找类型,如范围查找,是不能使用哈希索引的。因此这里出现no--hash searches的情况,通过hash searches:non-hash searches可以大概了解使用哈希索引后的效率

    由于自适应哈希索引是由InnoDB存储引擎自己控制的,因此这里的这些信息只仅供参考。不过可以通过参数innodb_adaptive_hash_index来禁用或启动此特性,默认是开启




    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 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下



    2. B-Tree索引 

          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 相邻的后一个 LeafNode 的指针信息,这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。 
          在 Innodb 存储引擎中,存在两种不同形式的索引,一种是 Cluster 形式的主键索引( Primary Key ),另外一种则是和其他存储引擎(如 MyISAM 存储引擎)存放形式基本相同的普通 B-Tree 索引,这种索引在 Innodb 存储引擎中被称为 Secondary Index 。下面我们通过图示来针对这两种索引的存放 
    形式做一个比较。 

        MySQL的btree索引和hash索引的区别 

          图示中左边为 Clustered 形式存放的 Primary Key ,右侧则为普通的 B-Tree 索引。两种 Root Node 和 Branch Nodes 方面都还是完全一样的。而 Leaf Nodes 就出现差异了。在 Prim中, Leaf Nodes 存放的是表的实际数据,不仅仅包括主键字段的数据,还包括其他字段的数据据以主键值有序的排列。而 Secondary Index 则和其他普通的 B-Tree 索引没有太大的差异,Leaf Nodes 出了存放索引键 的相关信息外,还存放了 Innodb 的主键值。 

          所以,在 Innodb 中如果通过主键来访问数据效率是非常高的,而如果是通过 Secondary Index 来访问数据的话, Innodb 首先通过 Secondary Index 的相关信息,通过相应的索引键检索到 Leaf Node之后,需要再通过 Leaf Node 中存放的主键值再通过主键索引来获取相应的数据行。MyISAM 存储引擎的主键索引和非主键索引差别很小,只不过是主键索引的索引键是一个唯一且非空 的键而已。而且 MyISAM 存储引擎的索引和 Innodb 的 Secondary Index 的存储结构也基本相同,主要的区别只是 MyISAM 存储引擎在 Leaf Nodes 上面出了存放索引键信息之外,再存放能直接定位到 MyISAM 数据文件中相应的数据行的信息(如 Row Number ),但并不会存放主键的键值信息









    About Me

    .............................................................................................................................................

    ● 本文作者:小麦苗,部分内容整理自网络,若有侵权请联系小麦苗删除

    ● 本文在itpub(http://blog.itpub.net/26736162/abstract/1/)、博客园(http://www.cnblogs.com/lhrbest)和个人微信公众号(xiaomaimiaolhr)上有同步更新

    ● 本文itpub地址:http://blog.itpub.net/26736162/abstract/1/

    ● 本文博客园地址:http://www.cnblogs.com/lhrbest

    ● 本文pdf版、个人简介及小麦苗云盘地址:http://blog.itpub.net/26736162/viewspace-1624453/

    ● 数据库笔试面试题库及解答:http://blog.itpub.net/26736162/viewspace-2134706/

    ● DBA宝典今日头条号地址:http://www.toutiao.com/c/user/6401772890/#mid=1564638659405826

    .............................................................................................................................................

    ● QQ群号:230161599(满)、618766405

    ● 微信群:可加我微信,我拉大家进群,非诚勿扰

    ● 联系我请加QQ好友646634621,注明添加缘由

    ● 于 2017-09-01 09:00 ~ 2017-09-30 22:00 在魔都完成

    ● 文章内容来源于小麦苗的学习笔记,部分整理自网络,若有侵权或不当之处还请谅解

    ● 版权所有,欢迎分享本文,转载请保留出处

    .............................................................................................................................................

    小麦苗的微店https://weidian.com/s/793741433?wfr=c&ifr=shopdetail

    小麦苗出版的数据库类丛书http://blog.itpub.net/26736162/viewspace-2142121/

    .............................................................................................................................................

    使用微信客户端扫描下面的二维码来关注小麦苗的微信公众号(xiaomaimiaolhr)及QQ群(DBA宝典),学习最实用的数据库技术。

       小麦苗的微信公众号      小麦苗的DBA宝典QQ群1     小麦苗的DBA宝典QQ群2        小麦苗的微店

    .............................................................................................................................................

    ico_mailme_02.png
    DBA笔试面试讲解群1
    DBA笔试面试讲解群2
    欢迎与我联系



    来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/26736162/viewspace-2144680/,如需转载,请注明出处,否则将追究法律责任。

    展开全文
  • 哈希索引

    千次阅读 2019-05-22 17:09:45
    哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是一个较小的值,并且不同键值的行计算出来的哈希码...

    哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是一个较小的值,并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。

    哈希索引可细分为静态哈希和动态哈希这两大类,先介绍静态哈希,然后再介绍动态哈希。

    静态哈希

    基于散列技术的文件组织使我们能够避免访问索引结构,同时也提供了一种构造索引的方法。在对散列的描述中,使用桶(bucket)来表示能存储一条或多条记录的一个存储单位。通常一个桶就是一个磁盘块,但也可能大于或者小于一个磁盘块。

    散列索引将散列函数作用于搜索码以确定对应的桶, 然后将此搜索码以及对应的指针存入此桶(或溢出桶)中。

    静态哈希.png

    【散列函数(hash function)】:令 K 表示所有的搜索码值的集合, 令 B 表示所有桶地址的集合,,散列函数 h 是一个从 K 到 B 的函数.。

    • 插入操作:计算 h(Ki),从而获得存放该记录的桶的地址,并将记录存储到该桶中;
    • 查找:计算 h(Ki),然后搜索具有该地址的桶;
    • 删除:计算 h(Ki),然后在相应的桶中查找此记录并从中删除它。

    【散列函数的特点】:

    • 理想的散列函数把存储的码均匀地分布到所有的桶中,使每个桶含有相同数目的记录。
    • 分布是均匀的:即散列函数从所有可能的搜索码值集合中为每个桶分配同样数量的搜索码值。
    • 分布是随机的:即在一般情况下, 不管搜索码值实际怎样分布, 每个桶应分配到的搜索码值数目几乎相同. 更确切地说, 散列值不应与搜索码的任何外部可见的排序相关, 例如按字母的顺序或按搜索码长度的顺序. 散列函数应该表现为随机的.

    桶溢出

    到目前为止,我们一直假设插入记录时,记录映射到的桶有存储记录的空间。若此时桶已经没有足够的空间,就会发生桶溢出现象。

    【产生原因】:

    • 桶不足:通数目(用 Nb 表示)的选择必须使 Nb > Nr/fr,其中 Nr 表示将要存储的记录总数,fr 表示一个桶能存放的记录数目。需要注意的是,这种表示是以记录总数已知为前提选择散列函数。
    • 偏斜:某些桶分配到的记录比其他桶多,所以即使其他桶仍有空间,某个桶也仍可能溢出,这种情况称为桶偏斜。偏斜发生的原因有两个:
      • 多条记录可能有相同的搜索码;
      • 所选的散列函数可能会造成搜索码的分布不均。

    【处理方案】:溢出链。

    桶的数目选为 (Nr / fr) * (1 + d),其中 d 为避让因子,取值一般约为 0.2。相当于增加了桶的数目(若桶的数目不为整数,则向上取整),虽然有一些空间会浪费,但在一定程度上减少了溢出的可能性。

    需要明确的是:尽管分配的桶比所需的桶多一些,但是桶溢出还是可能发生。我们用溢出桶(多出来的那些桶)来处理桶溢出问题。具体过程如下:如果一条记录必须插入桶 b,而桶 b 此时已满,系统会提供另一个溢出桶来存储该记录。如果溢出桶也满了,再提供另一个溢出桶,如此循环。

    一个给定桶的所有溢出桶用一个链表链接在一起,使用这种链表的溢出处理称为溢出链

    溢出链.png

    为了处理溢出链, 我们需要将查找算法做轻微的改动。和前面一样,系统使用搜索码上的散列函数来确定一个桶 b,系统必须检查桶 b 中所有的记录,看是否有匹配的搜索码。此外,如果桶 b 有溢出桶,则系统还要检查桶 b 的所有溢出桶中的记录。

    静态哈希的缺点

    静态散列最大的缺点在于必须在实现系统时选择确定的散列函数。此后若被索引的文件变大或缩小,要想再改变散列函数就不容易了。因为散列函数 h 将搜索码值映射到桶地址的固定集合 B 上:

    • 根据当前文件大小选择散列函数,这样的选择会使得性能随着数据库的增大而下降。换言之,初始时集合 B 太小,一个桶就会包含许多不同的搜索码值的记录,从而可能发生桶溢出。当文件变大时,性能就会受到影响。
    • 根据将来某个时刻文件的预计大小选择散列函数。 尽管这样可以避免性能下降,但是初始时会造成相当大的空间浪费。

    虽然我们可以随着文件增大,周期性地对散列结构进行重组。这种重组涉及一系列问题:

    • 包括新散列函数的选择;
    • 在文件中每条记录上重新计算散列函数;
    • 分配新的桶。

    重组是一个规模大、耗时的操作,而且重组期间必须禁止对文件的访问。所以我们需要解决的问题就是如何动态地改变桶的数目和散列函数。

    动态哈希

    针对静态散列技术出现的问题,动态散列(dynamic hashing)技术允许散列函数动态改变,以适应数据库增大或缩小的需要,下面介绍可扩充散列(extendable hashing)。

    可扩充散列

    当数据库增大或缩小时,可扩充散列可以通过桶的分裂或合并来适应数据库大小的变化,这样可以保持空间的使用效率。此外,由于重组每次仅作用于一个桶,因此所带来的性能开销较低。

    【做法】:

    • 选择一个具有均匀性和随机性特性的散列函数 h。此散列函数产生的值范围相对较大,是 b 位二进制整数,一个典型的 b 值是 32。
    • 把记录插入文件时按需建桶,用小于等于 b 的 i 个位用作附加桶地址表中的偏移量,i 的值会随着数据库大小的变化而增大或者减少。

    可扩充散列.png

    查询操作

    【过程】:查找包含搜索关键字 k 的存储桶。

    1. 计算 h(k) = X;
    2. 使用 X 的前 i 个高位作为存储区地址表的偏移量,并按指针指向相应的存储区。

    插入操作

    【过程】:插入具有搜索关键字 k 的记录。

    1. 按照查询操作找到存储桶,假设定位到桶编号为 j。如果该存储桶仍然有空间,则在该存储桶中插入记录,否则必须拆分存储桶,并将该桶中现有记录和新记录一起进行重新分配。为了拆分该存储桶,系统必须先根据散列值确定是否需要增加所使用的位数。
    2. 然后根据 i(global depth)和 ij(local depth)的大小关系进行相应的操作。
      • 如果 i = ij,那么在桶地址表中只有一个指向桶 j 的指针,所以系统需要增加桶地址表的大小。以容纳由于桶 j 分裂而产生的两个桶指针。为了达到这个目的,系统可以将 i 的值加 1,从而使桶地址表的大小加倍。这样,原表中每个表项都被两个表项替代,两个表项都包含和原表项一样的指针。现在桶地址表中有两个表项指向桶 j。系统重新分配一个桶(桶z),并让第二个表项指向此新桶。桶 j 中的各条记录重新散列, 根据前 i 位(i 已经加1)来确定该记录是放在桶 j 中还是放在新创建的桶中。
      • 如果 i > ij,那么就有多个表项(指针) 指向桶 j。因此,不需要扩大桶地址表就可以分裂桶 j。指向桶 j 的所有表项的索引前缀的最左 ij 位相同。系统分配一个新桶(桶 z),将 ij 和 iz 置为原 ij 加 1 后得到的值。然后系统需要调整桶地址表中原来指向桶 j 的表项。系统让这些表项的前一半保持原样(指向桶 j),而后一半指向新创建的桶 (桶 z)。然后桶 j 中的各条记录重新被散列,分配到桶 j 或者桶 z 中。

    【示例】:假设现在有如下三条搜索码值,h(k1) = 100100,h(k2) = 000110,h(k3) = 110110。先假设桶的大小为 1,并插入前两项 k1 和 k2,可以通过最左边的位值进行区分,得到如下图所示的结果。

    可扩充散列插入操作图示1.png

    接着,插入第三项,此时左边第一位已经无法区分了,所以将 i 增加 1,此时刚好可以将三个搜索码进行区分,见下图。

    可扩充散列插入操作图示2.png

    k1 和 k3 可通过 10 和 11 进行区分,以 0 作为第一位的不需要进行比较,所以 00 和 01 都是指向 k2。

    现在需要插入一条新的搜索码值 h(k4) = 011110。前两位为 01 指向了桶 A,但桶 A 已满,所以需要进行分裂。因为没有更多的搜索码指向桶 A,所以 i 不需要增加,属于 i > ij 的情况,仅需要将桶 A 进行分裂,令 ij + 1,并重新进行分配。

    可扩充散列插入操作图示3.png

    如果,h(k2) = 010110,也就是说 k2 和 k4 都指向桶 D,并且桶 D 已满,更多的搜索码指向桶 D,属于 i = ij 的情况,所以需要将 i 加 1,用左边的三位来作为桶地址。现在将桶 D 分裂,变成 D’ 和 E,并重新进行散列操作,将 k2 放到 D’ 桶中,k4 放到 E 桶中。

    可扩充散列插入操作图示4.png

    删除操作

    【过程】:删除一条搜索码值为 k 的记录。

    系统先查找到对应的桶,设为桶 j。系统不仅要把搜索码从桶中删除,还要把记录从文件中删除。如果这时桶为空了,那么也要将桶删除掉。

    需要注意的是,此时某些桶可能合并(就是与具有相同 ij 值和相同 ij -1 前缀的桶合并),桶地址表的大小也可以减半。


    通过上述分析可总结出动态散列的优缺点。

    【优点】:

    • 随着记录的增加, 动态散列的性能并不会下降;
    • 动态散列有着最小的空间开销。

    【缺点】:

    • 会增加一次额外的查询定位, 因为在查询桶本身之前还需要查找目录来定位桶;
    • 存储区地址表本身可能变得很大;
    • 更改存储区地址表的大小是一项代价昂贵的操作。

    比较分析

    顺序索引和散列索引的比较分析

    【散列索引】:

    • 在数据库中查找一个值的效率更高;
    • 没有办法利用索引完成排序;
    • 在有大量重复值的时候,散列索引的效率也是极低的,因为存在哈希碰撞的情况。

    【顺序索引】:在指出了一个值范围的查询中比散列索引更可取。

    如果存储的数据重复度很低(也就是说基数很大),对该列数据以等值查询为主,没有范围查询、没有排序的时候,特别适合采用散列索引;大多数情况下,会有范围查询,排序、分组等查询特征,就用顺序索引。

    B+ 树索引和哈希索引的比较分析

    【B+ 树】:

    • 所有的值都是按照顺序存储的,并且每一个叶子页到根的距离相同;
    • 适用于全键值、键值范围或者键前缀查找。顺序索引技术在指出了一个值范围的查询中比散列索引更可取。

    【哈希索引】:基于哈希表实现,只有精确匹配索引所有列的查询才有效。

    • 索引自身只需要存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快。
    • 缺点:
      • Hash索引能使用范围查询;
      • 数据库无法利用Hash索引的数据来避免任何排序运算;
      • Hash索引任何时候都不能避免表扫描。

    Q&A

    问:顺序索引与散列索引的适用场景?

    这两种索引结构都有其优缺点,如果是 select * from a where b=c 这样的定值查询,散列比顺序索引跟适合,顺序索引会随着记录数的增加而性能降低,散列则相对稳定。而对于 where b > c and b < d 这样的范围搜索,则顺序索引更适合,散列的随机特性使得无法定位搜索的桶。所以散列只适合根据搜索码搜索且不是范围查询的场合。

    问:可扩充散列为什么需要局部深度和全局深度?

    可扩展散列允许目录的大小增加或减少,具体取决于插入和删除的数量和种类。

    目录大小更改后,应用于搜索键值的哈希函数也应更改。 因此索引中应该有一些关于要应用哪个哈希函数的信息。 此信息由全局深度提供。

    目录大小的增加不会导致为每个新目录条目创建新存储桶。 每当要拆分由两个或多个目录条目共享的存储桶时,目录大小不需要加倍。这意味着对于每个存储桶,我们需要知道它是由两个或多个目录条目共享。 此信息由存储桶的局部深度提供。(目录:桶地址表)

    总结

    哈希索引思维导图.png

    参考

    展开全文
  • 哈希索引(memory支持) memory:基于内存的存储引擎 哈希表在可控的冲突范围,我们经常写的链式哈希表,它的增删改查的时间复杂度都是O(1) 哈希索引,基于哈希表这个数据结构实现的 链式哈希表: 平衡树的增删改查...

    哈希索引(memory支持)

    memory:基于内存的存储引擎
    哈希表在可控的冲突范围,我们经常写的链式哈希表,它的增删改查的时间复杂度都是O(1)
    哈希索引,基于哈希表这个数据结构实现的
    链式哈希表:

    平衡树的增删改查的时间复杂度是O(logn)
    B+树索引就是把磁盘上的存储的索引加载到内存上构建的数据结构,索引就是数据结构。

    看起来哈希表比B+树好。
    但是为什么MyISAM和InnoDB存储引擎用的是B+树索引?

    我们主要看
    1、搜索的效率:
    2、磁盘I/O的花费:

    我们改用创建哈希索引来看看
    在这里插入图片描述
    实际上,show create 只是显示你创建索引的标志,底层到底是不是哈希索引是不准的

    这个是准的
    在这里插入图片描述
    都是B+树

    假设现在默认存储引擎是memory

    默认选择的是哈希索引
    在这里插入图片描述
    构建链式哈希表
    根据选定的哈希函数,把每一行记录的name字段作为参数来求一个哈希值
    ,哈希值相当于桶的序号。(哈希冲突)
    解决哈希冲突:在桶里面用链表串起来。
    在这里插入图片描述
    哈希表的增删查效率高,是O(1),但是哈希表中的元素没有任何顺序可言。
    意味着如果用哈希表来构建索引的话,我们只能进行等值比较。

    在这里插入图片描述
    像上面这个,就用不着索引了。
    不能确保
    在这里插入图片描述
    在一个桶中
    对于哈希表来说,不能做范围搜索和前缀搜索和order by
    在哈希表中,不同元素,哪怕是15和16,很近,通过求哈希值,模上一个桶的个数,可能就不在一个桶中了。

    如果用链式哈希表构建索引,一个桶里面的节点代表1次磁盘I/O,除非是等值搜索,不然就太慢了。
    哈希索引只适用于数据都在内存上,仅仅适合等值查询。
    不能为我们减少磁盘I/O的次数
    在这里插入图片描述

    InnoDB自适应哈希索引

    在这里插入图片描述
    如果 InnoDB存储引擎监测到同样的二级索引不断被使用(select *,要回表,要搜主键索引树),那么它会根据这个二级索引在内存上根据二级索引树(B+树)上的二级索引的值,在内存上构建1个哈希索引来加速搜索(只有等值比较)
    O(1)的时间复杂度就访问到name了,然后直接访问它的数据data指针,就可以速度更快了

    自动的功能,优化的功能,加快搜索
    在这里插入图片描述
    蓝色的箭头先搜二级索引树,再通过二级索引树找到主键,再通过主键索引树找到相应的数据页。现在是用二级索引直接构建哈希索引了,name=‘zhangsan’,通过这个哈希表找到‘zhangsan’直接得到data的指针了,就是图中的黄色箭头,直接访问到数据页了。
    省了二级索引树和主键索引树的搜索过程
    对B+树上频繁使用二级索引搜索并且进行回表操作的优化!
    hash索引的生成和维护也是耗费性能的我们有参数指标,通过参数指标查看,如果自适应哈希索引可以提供效率,那我们使用它,如果它成为性能的损坏,我们就关闭自适应哈希索引。
    自适应哈希索引并不能绝对的在任何场景下提高对二级索引搜索的效率
    分区:要是在一个链表或者数组进行并行操作,只能加锁。要是在不同的桶操作,就不用加锁。
    每一个索引被分到1个分区。
    在这里插入图片描述
    默认开启

    在MySQL 5.7中,对自适应哈希索引搜索系统进行了分区。每个索引都绑定到一个特定的分区,并且每个分区都由单独的锁存器保护。
    分区由innodb _ adaptive _ hash _ index _ parts配置选项控制。在…里
    在早期版本中,自适应散列索引搜索系统由一个锁存器保护,该锁存器
    在繁重的工作负载下可能会成为争夺点。这innodb _ adaptive _ hash _ index _ parts选项默认设置为8。最大设置为512。
    哈希索引总是基于表上现有的B+树索引构建的InnoDB可以构建一个
    为B树定义的任何长度的关键字的前缀上的散列索引

    这取决于InnoDB观察到的B树索引的搜索模式。散列索引可以是部分的,只覆盖索引中那些经常被访问的页面。
    您可以监视自适应哈希索引的使用以及在SHOW ENGINE INNODB STATUS命令输出的信号量部分。如果你看到许多线程在等待btr0sea.c中创建的读写锁,那么禁用它可能是有用的自适应散列索引。
    在这里插入图片描述

    分区:
    在这里插入图片描述
    5.7以后,每个分区都有1把锁

    展开全文
  • 哈希算法应用场景

    2019-09-28 10:31:30
    哈希算法        将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。    &...
  • 自适应哈希索引

    2017-03-27 11:49:18
    InnoDB存储引擎会监控对表上索引的查找,如果观察到建立哈希索引可以带来速度的提升,则建立哈希索引,所以称之为自适应(adaptive)的。自适应哈希索引通过缓冲池的B+树构造而来,因此建立的速度很快。而且不需要将...
  • InnoDB的哈希索引

    2020-02-24 15:54:03
    (1)使用InnoDB存储引擎的用户无法手动创建哈希索引,这一层上说,InnoDB确实不支持哈希索引; (2)InnoDB会自调优(self-tuning),如果判定建立自适应哈希索引(Adaptive Hash Index, AHI),能够提升查询效率,...
  • 索引是在存储引擎层实现的,而不是在服务器层实现的,所以不同存储引擎具有不同的索引类型和实现。 1.1 B+Tree 索引 是大多数 MySQL 存储引擎的默认索引类型。 因为不再需要进行全表扫描,只需要对树进行搜索即可...
  • InnoDB支不支持哈希索引? 对于InnoDB的哈希索引,确切的应该这么说: (1)InnoDB用户无法手动创建哈希索引,这一层上说,InnoDB确实不支持哈希索引; (2)InnoDB会自调优(self-tuning),如果判定建立自适应哈希...
  • B+树索引和哈希索引

    2020-09-06 16:00:11
    在MySQL里常用的索引数据结构有B+树索引和哈希索引两种,我们来看下这两种索引数据结构的区别及其不同的应用建议。 二者区别 备注:先说下,在MySQL文档里,实际上是把B+树索引写成了BTREE,例如像下面这样的写法...
  • 一致性哈希算法 应用场景

    千次阅读 2014-07-25 14:02:36
    一致性哈希算法 应用场景(转) 原创文章,转载请注明: 转载自LANCEYAN.COM 本文链接地址: 一致性hash和solr千万级数据分布式搜索引擎中的应用 互联网创业中大部分人都是草根创业,这个时候没有强劲的...
  • 文章目录索引什么是索引使用场景常见的索引哈希索引自适应哈希索引B+树索引全文索引索引的使用 索引 什么是索引 在数据库中,表、数据、索引之间的关系就类似于书籍、书籍内容、书籍目录。 倘若不使用索引,则MySQL...
  • 文章目录索引引言常见的索引哈希索引自适应哈希索引 索引 引言 为什么需要索引? 倘若不使用索引,查找数据时,MySQL必须遍历整个表。而表越大,查询的时间则越长,则数据库的效率也就越低。而索引就类似于书籍的...
  • mysql索引类型与数据存储一、... 查询语句五、BTree索引和哈希索引的区别 一、innodb索引与myisam索引存储数据的区别 myisam索引(MYI)与数据(MYD)分开存储,叫做非聚集索引(UnClustered Index) innodb数据与索引
  • 上图可以看出: InnoDB使用哈希索引来实现自适应哈希索引功能 2. 描述 InnoDB引擎有一个页数的功能叫做自适应哈希索引。 当InnoDB注意到某些索引值被使用非常频繁的时候,它会在内存中基于B-Tree索引之上再...
  • Mysql 哈希索引(hash index)

    千次阅读 2020-07-13 17:42:36
    哈希索引本身在实际项目中使用的并不多,但是常常在面试的时候拿来与B+Tree 索引等进行比较提问,那么哈希索引到底是怎样的结构?又适用于哪些场景呢?有哪些优点和缺点呢? 结构实现 哈希索引(hash index) 是基于...
  • 文章目录索引索引使用场景B+树索引聚集索引非聚集索引 索引 在数据库中,表、数据、索引之间的关系就类似于书籍、书籍内容、书籍目录。 倘若不使用索引,则MySQL必须遍历整个表,直到找到数据,而表越大,查询的...
  • 在MySQL里常用的索引数据结构有B+树索引和哈希索引两种,我们来看下这两种索引数据结构的区别及其不同的应用建议。 二者区别 备注:先说下,在MySQL文档里,实际上是把B+树索引写成了BTREE,例如像下面这样的写法:...
  • 在MySQL里常用的索引数据结构有B+树索引和哈希索引两种,我们来看下这两种索引数据结构的区别及其不同的应用建议。 二者区别 备注:先说下,在MySQL文档里,实际上是把B+树索引写成了BTREE,例如像下面这样的...
  • Innodb 自适应哈希索引的优缺点

    千次阅读 2019-01-16 18:10:20
    适合使用场景 适合使用 = 和 IN 操作符的等值查询 不合适场景 不适合使用 like 和 % 的范围查询和高并发的joins 优点 提高了Innodb的内存使用率和一些情况下二级索引的查询效率 缺点 占用Innodb的内存缓存,...
  • 理解B树索引和哈希索引的数据结构能够帮助预测不同的存储引擎上查询有怎么样的不同,使用这些数据结构在他们的索引上,特别是内存存储引擎让你选择是用B树索引还是哈希索引。 B树索引的特点 一个B树索引能够用于列...
  • 在MySQL里常用的索引数据结构有B+树索引和哈希索引两种,我们来看下这两种索引数据结构的区别及其不同的应用建议。 二者区别 备注:先说下,在MySQL文档里,实际上是把B+树索引写成了BTREE,例如像下面这样的写法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 47,572
精华内容 19,028
关键字:

哈希索引应用场景