AntDB-M高性能设计之hash索引动态rehash

原创
2023/11/10 10:45
阅读数 23

AntDB-Mhashbtreehashhashhash1hashhashhashhash

 

        1hash table

 

使 select * from table where a = value; valuehashhashhashavalue

 

hash

 

struct node{        uint8            oid;   // value        node *    node_prev;  //         node *    node_next;  // }

 

sizeof(node) 8+8+8 =24

 

AntDB-Mhashmnhashnhashhashmhash n*(hash + m*24)24

 

 

AntDB-M hash

 

AntDB-M使

 

struct array_node{uint8   prev_oid;   // uint8   next_oid;   // }

 

sizeof(array_node) 8+8 =16oid0narray_node[n]array_node[k]k

 

  • 访array_node[k]. prev_oidarray_node[k]. next_oid

  • array_node[k]k访kuint8 oid()1/3hash2/3

 

 

mhashbucketn(nm)hashnuint8 bucket_head[n], bucket_head(array_node)array_node[m], bucket

 

hash, 32936815223, array_node3

 

bucket_head[2]=3array_node [3] ->prev_oid=0          array_node [3] -> next_oid=29array_node [29] ->prev_oid=3               array_node [29] ->next_oid=36815array_node [36815] ->prev_oid=29array_node [36815] ->next_oid=0

 

(next_oid=0)访

 

10005000hashbucket1000bucket5hashrehashhashhashhash table

 

 

AntDB-M rehash

 

2hashlockmigrate_nodebucketbucketbucketbucketmigrate_nodebucket.

 

1. hash_tablehash_table

 

2. hash_table, hash_tablehash_table

 

3. hash_tablehash_table;

 

 

2AntDB-Mrehash

 

rehashhash table(++)hashbucket

 

3rehashfind

 

 

4rehashinsert

 

 

 

hashAntDB-MAntDB-Mhashhash使hash

 

hashrehash使AntDB-Mhash

 

AntDB

 

AntDB2008AntDB-MAntDB2410亿线15

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部