fumidb/api/index.md

索引格式

int8

查找速度为O(1)

由于总条目仅有256条，因此直接存储256个uint64的位置指针，指示该条目在文件的偏移。

下面每格1字节

┌─────────┬─────────┬─────────┬─────────┐
│ ptr 000 │ ptr 001 │ ptr ... │ ptr 255 │
└─────────┴─────────┴─────────┴─────────┘

当值可重复时，索引指向的是一个链表的头，详见types。

int16

查找速度为

• 无该表项：O(1)
• 有该表项：O(logn)

由于总条目仅有65536条，因此使用位图索引+位图+顺序链表进行查找定位。

位图与位图索引

每一位代表一个槽位，为0表示当前为空，为1表示当前已有值，按顺序排列，占用文件中的65536/8/4096=2页空间。

下面每格1字节

┌────────┬────────┬────────┬────────┐
│00100011│00000000│........│11000110│
└────────┴────────┴────────┴────────┘

每256位（32字节）为一组，生成8位（1字节）位图索引，其数字值表示在这256个槽位中有多少个已被填充。总共有256组索引，作为第一级index，单独在一个块存放，并在开头添加3个分别指向2页索引起始和顺序链表起始的指针。特别地，如果256个槽位均被填满，索引也为0，因此还需要额外判断其对应位图是全空还是全满。只要有一处不为0而位图索引为0，即可判定这256个槽位全满。

下面每格1字节

┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│         pointer of first index page start  ( this pointer will never be zero )        │
├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│         pointer of second index page start ( this pointer will never be zero )        │
├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│            pointer of index chain start ( this pointer will never be zero )           │
├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│   0000   │   0045   │   0100   │   0065   │   0000   │   ....   │   0033   │   0000   │
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘

顺序链表

根据位图和位图索引可以很方便地计算出当前值在顺序链表上的位置。顺序链表以256个uint64的位置指针(半页)为单位分配，当装满后分配一块新的空间，并将新链表开头的位置指针记录在旧链表开头。当没有下一个节点时，开头置0。特别地，当删除表项时，节点数有可能减少。此时并不归还多余节点所占空间，也不对节点头部指针做任何改动，而是将其保留以备后用。

下面每格8字节

┌────────┬────────┬────────┬────────┐
│next ptr│ ptr000 │ ptr... │ ptr255 │
└────────┴────────┴────────┴────────┘

当值可重复时，索引指向的是一个链表的头，详见types。

int32/float

查找速度为O(logn)

• 使用B+树建立索引，每个节点大小为4096字节，最多可有n=341个扇出，340个值；最少则有170个值（根节点不遵守最少值规则）。

下面每格4字节, next node ptr 将所有块连接起来以便全部遍历(如删除)。

    0                   8        12                  20
    ┌───────────────────┬─────────┬───────────────────┬─────────┐
   0│    pointer 001    │ key 001 │    pointer 002    │ key 002 │
    ├───────────────────┼─────────┼───────────────────┼─────────┤
  24│    pointer 003    │ key 003 │    pointer 004    │ key 004 │
    ├───────────────────┼─────────┼───────────────────┼─────────┤
  48│    pointer 005    │ key 005 │    pointer 006    │ key 006 │
    ├───────────────────┼─────────┼───────────────────┼─────────┤
 xxx│    pointer xxx    │ key xxx │    pointer xxx    │ key xxx │
    ├───────────────────┼─────────┼───────────────────┼─────────┤
4056│    pointer 339    │ key 339 │    pointer 340    │ key 340 │
    ├───────────────────┼─────────┴─────────┬─────────┴─────────┘
4080│    pointer 341    │   next node ptr   │
    └───────────────────┴───────────────────┘
                     4088                4096

备选方案

• 使用哈希桶作索引，允许溢出桶，同样每个桶大小为4096字节，可装340个值。共256个桶，初始占用1M空间，后续由于溢出可能会增加。
• 哈希算法: hash = (n*(n+11454191981))%256

    0                   8        12                  20
    ┌───────────────────┬─────────┬───────────────────┬─────────┐
   0│    pointer 001    │ key 001 │    pointer 002    │ key 002 │
    ├───────────────────┼─────────┼───────────────────┼─────────┤
  24│    pointer 003    │ key 003 │    pointer 004    │ key 004 │
    ├───────────────────┼─────────┼───────────────────┼─────────┤
  48│    pointer 005    │ key 005 │    pointer 006    │ key 006 │
    ├───────────────────┼─────────┼───────────────────┼─────────┤
 xxx│    pointer xxx    │ key xxx │    pointer xxx    │ key xxx │
    ├───────────────────┼─────────┼───────────────────┼─────────┤
4056│    pointer 339    │ key 339 │    pointer 340    │ key 340 │
    ├───────────────────┼─────────┴─────────┬─────────┴─────────┘
4080│   overflow  ptr   │   next node ptr   │
    └───────────────────┴───────────────────┘
                     4088                4096

int64/double

查找速度为O(logn)

• 使用B+树建立索引，每个节点大小为4096字节，最多可有n=256个扇出，255个值；最少则有128个值（根节点不遵守最少值规则）。

下面每格8字节, next node ptr 将所有块连接起来以便全部遍历(如删除)。

    0                   8
    ┌───────────────────┬───────────────────┐
   0│    pointer 001    │      key 001      │
    ├───────────────────┼───────────────────┤
  16│    pointer 002    │      key 002      │
    ├───────────────────┼───────────────────┤
  32│    pointer 003    │      key 003      │
    ├───────────────────┼───────────────────┤
 xxx│    pointer xxx    │      key xxx      │
    ├───────────────────┼───────────────────┤
4064│    pointer 255    │      key 255      │
    ├───────────────────┼───────────────────┤
4080│    pointer 256    │   next node ptr   │
    └───────────────────┴───────────────────┘
                     4088                4096

备选方案

• 使用哈希桶作索引，允许溢出桶，同样每个桶大小为4096字节，可装255个值。共1024个桶，初始占用4M空间，后续由于溢出可能会增加。
• 哈希算法: hash = (n*(n+18446744073709551557))%1024

    0                   8
    ┌───────────────────┬───────────────────┐
   0│    pointer 001    │      key 001      │
    ├───────────────────┼───────────────────┤
  16│    pointer 002    │      key 002      │
    ├───────────────────┼───────────────────┤
  32│    pointer 003    │      key 003      │
    ├───────────────────┼───────────────────┤
 xxx│    pointer xxx    │      key xxx      │
    ├───────────────────┼───────────────────┤
4064│    pointer 255    │      key 255      │
    ├───────────────────┼───────────────────┤
4080│   overflow  ptr   │   next node ptr   │
    └───────────────────┴───────────────────┘
                     4088                4096

string

查找速度为O(logn)

先将其哈希为int64再按int64进行查找。具体哈希方法为取字符串md5的前8位作为小端uint64。冲突时，根据string表项附带存储的下一个哈希相同的数据项的指针(uint64)可依次遍历到所有项目，然后找到真正与查询内容相同的项。