mysql内核分析--innodb哈希表的内部实现(上)


1.哈希表的概述

   hash表的实现是innodb的基础功能之一，通过关键值进行映射，从而迅速进行查询、插入、删除的操作。

   hash表算法，在数据库内核里面被广泛的使用，举个例子，这个结构将会在下文中继续使用的。

/* Data structure for a column in a table */

struct dict_col_struct{

       hash_node_t   hash;       /* hash chain node */

       ulint        ind;  /* table column position (they are numbered

                            starting from 0) */

       ulint        clust_pos;/* position of the column in the

                            clustered index */

       ulint        ord_part;/* count of how many times this column

                            appears in ordering fields of an index */

       const char*    name;      /* name */

       dtype_t           type;       /* data type */

       dict_table_t*   table;       /* back pointer to table of this column */

       ulint        aux; /* this is used as an auxiliary variable

                            in some of the functions below */

};

   从数据结构的名称上来看，这个关于列结构的，具有相同hash值的col结构，通过hash字段进行连接。该字段的定义如下：

typedef void*  hash_node_t;

  col结构里面的其它字段表明该列的一些属性：name表示列名，type表明列的值类型，table表明该列所属的表结构。



2.数据结构

typedef struct hash_table_struct hash_table_t;

typedef struct hash_cell_struct hash_cell_t;



typedef void*  hash_node_t;



/* The hash table structure */

struct hash_table_struct {

       ibool              adaptive;/* TRUE if this is the hash table of the

                            adaptive hash index */

       ulint        n_cells;/* number of cells in the hash table */

       hash_cell_t*    array;      /* pointer to cell array */

       ulint        n_mutexes;/* if mutexes != NULL, then the number of

                            mutexes, must be a power of 2 */

       mutex_t* mutexes;/* NULL, or an array of mutexes used to

           &nb