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

Matthewl

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
protect segments of the hash table */
mem_heap_t** heaps; /* if this is non-NULL, hash chain nodes for
external chaining can be allocated from these
memory heaps; there are then n_mutexes many of
these heaps */
mem_heap_t* heap;
ulint magic_n;
};

struct hash_cell_struct{
void* node; /* hash chain node, NULL if none */
};

1）创建hash表
n_cells表明hash表的大小，我们都知道hash表常用的是进行素数的模操作。先看下创建hash表的函数的实现。
/*****************************************************************
Creates a hash table with >= n array cells. The actual number of cells is
chosen to be a prime number slightly bigger than n. */

hash_table_t*
hash_create(
/*========*/
/* out, own: created table */
ulint n) /* in: number of array cells */
{
hash_cell_t* array;
ulint prime;
hash_table_t* table;
ulint i;
hash_cell_t* cell;

prime = ut_find_prime(n);

table = mem_alloc(sizeof(hash_table_t));

array = ut_malloc(sizeof(hash_cell_t) * prime);

table->adaptive = FALSE;
table->array = array;
table->n_cells = prime;
table->n_mutexes = 0;
table->mutexes = NULL;
table->heaps = NULL;
table->heap = NULL;
table->magic_n = HASH_TABLE_MAGIC_N;

/* Initialize the cell array */

for (i = 0; i < prime; i++) {

cell = hash_get_nth_cell(table, i);
cell->node = NULL;
}

return(table);
}
在创建hash表的时候，我们提供的常用是一个普通的数字，来指明hash表的大小。这个n的值可能不是素数，所以需要通过ut_find_prime(n)来产生一个稍大于n的素数，当然这个素数不一定是大于n的最小素数。ut_find_prime的具体实现见文件ut0rnd.c。
接着调用mem_alloc函数来分配hash表结构，为该结构分配空间，这个比较简单。接着分配数量为prime个的hash单元，并通过后面的循环语句将单元的node指针置为空。

2)基础的函数
提供值之后，我们需要进行映射，获取对应的单元的编号。
/******************************************************************
Calculates the hash value from a folded value. */
UNIV_INLINE
ulint
hash_calc_hash(
/*===========*/
/* out: hashed value */
ulint fold, /* in: folded value */
hash_table_t* table) /* in: hash table */
{
return(ut_hash_ulint(fold, table->n_cells));
}
其中ut_hash_ulint函数的实现如下：
/***********************************************************
The following function generates a hash value for a ulint integer
to a hash table of size table_size, which should be a prime
or some random number for the hash table to work reliably. */
UNIV_INLINE
ulint
ut_hash_ulint(
/*=========*/
/* out: hash value */
ulint key,  /* in: value to be hashed */
ulint table_size)  /* in: hash table size */
{
key = key ^ UT_HASH_RANDOM_MASK2;

return(key % table_size);
}
通过模操作获得了对应的hash表单元的数值，然后就可以通过该数值找到hash表的该单元节点，调用hash_get_nth_cell函数，函数实现如下：
/****************************************************************
Gets the nth cell in a hash table. */
UNIV_INLINE
hash_cell_t*
hash_get_nth_cell(
/*==============*/
  /* out: pointer to cell */
hash_table_t*  table, /* in: hash table */
ulint  n) /* in: cell index */
{
ut_ad(n < table->n_cells);

return(table->array + n);
}