treee下载 - treee源代码下载

treee

其他源码

Update with Windows10 and MacOS executables

下载

树

通过Hashed ID标识并存储在不变的文件中的数据的快速索引引擎

这是Treee™索引引擎的GO实现。这既是用于您的GO项目中的模块的库，又是可执行的，可以用作HTTP的微服务。

动机

面临的挑战是，当数据是某些可以在子链中相互连接的项目列表时，要建立一个功能强大且安全的搜索引擎，通过其标识符进行索引，这些项目仅由Hashed值（例如SHA-256字符串表示）组成，并且所有存储在不可分的文件中。

它的最佳应用程序是一个区块链文件，其中项目是嵌入智能合约的交易，以及随后的用途和/或修改此智能合约的每个项目的每个子链。因此，Treee™索引目前用于ROOOT™区块链中。

正式描述

我们在这里定义了一种算法，用于基于标识符的标识符索引系统，该标识符同时对写作和阅读非常有力。

1）索引如何工作

Treee™索引被构造为无环图（树）。每个节点都包含节点地址（其儿子）或一组叶子，该叶子与有助于检索一个或多个链接项目的信息相对应。

节点的儿子数量是确定性的，取决于树的深度。我们用深度1的节点儿子的数量表示，在深度2，在深度上，节点的儿子数量。

目的是创建一个平衡的树，其宽度具有自适应以减小深度并优化性能。我们正在寻找索引编号，在这种情况下，项目的唯一标识符的数值值。

让我们解释一下索引的过程。

对于二进制树，我们以二进制形式（例如100 ）编写数字，该数字指示其在树上的位置。

在步骤中，如果位是0 ，我们将孩子传递给孩子，否则如果位是1 ，则将其传递给孩子。当节点是叶子时，我们停止。

对于树，我们通过一系列数字来构建该数字的表示形式，并以相同的方式穿越树。在深度步骤中，如果代表为0 ，我们将孩子传给孩子，如果代表是1 ，如果代表为1，则将其传递给孩子。当节点是叶子时，我们停止。

为了构建数字的表示，我们将依次采用质数的模型。根据中国遗骸的定理，每个数字都有一个独特的代表，可以写为这些模量的延续。确实，可以以以下形式写入数字：

项目标识符的值（其编号）表示为调制号码。用于固定尺寸整数计算模量。由于乘法比除法快（计算模型所需的速度），因此可以通过浮动使用乘法：。

鉴于数字的随机性质（或伪随机，由于项目的标识符是由加密哈希技术生成的），因此树是平衡的。要以恶意的方式使树不平衡，必须能够产生hashes的模仿遵循特定轨迹的哈希。但是，这种操作的困难呈指数增加（深度为were的顺序）。提醒您，前16个质数的产物等于。因此，一旦该索引包含相当大的数据，如果可能的话，以恶意的方式不平衡树就变得越来越不可能。

叶子包含以下有关项目的信息列表：

当前项目的标识符作为哈希字符串；
位置：文件中当前项目的启动地址；
大小：文件中保存项目的大小（以字节）；
来源：该项目子链原点的唯一标识符；
上一篇：链接到它的先前项目的唯一标识符；
下一步：可选地，下一个项目的唯一标识符。

下一个项目字段为空的叶子是子链中的最后一项。

其原点项目字段等于当前项目的标识符的叶子必然是子链的原点。因此，它具有特定的操作，此后，如果此后要有一个或多个项目，则该子链的最后一项将在这里确定为上一项。因此，叶子的最后三个字段对应于圆形链接列表。

2）使用索引

为索引添加一个元素：

新叶子写在索引中；
我们更新了先前与子链的最后一项相对应的叶子的“下一个”字段；
我们通过编写当前项目的标识符来修改原始项目的叶片的“以前”字段。

在索引中读取/搜索项目：

我们在树中发现与搜索项目的标识符相对应的叶子：
- 如果叶子的“下一个”字段是空的，这是子链的最后一项；
- 否则，我们将转到下一步；
我们发现叶子对应于“原点”字段的标识符；
我们使用此叶子的“以前”字段查找子链的最后一项。

使用索引时，我们可以看到，我们最多可以执行3次读取或3个写入和索引运行，而索引中的项目数在哪里。

有关更多详细信息，请随时阅读完整的白皮书。

用法

$ go get github.com/cyrildever/treee

 import (
  "github.com/cyrildever/treee/core/index"
  "github.com/cyrildever/treee/core/index/branch"
  "github.com/cyrildever/treee/core/model"
)

// Instantiate default index (could be any prime number up to the 1000th existing prime number,
// but should be much lower to better leverage the solution, and if 0 will use the default INIT_PRIME value)
treee , err := index . New ( index . INIT_PRIME )
if err != nil {
  // Handle error
}

// Add to index
leaf := branch. Leaf {
  ID : model . Hash ( "1234567890abcdef" ),
  Position : 0 ,
  Size : 100 ,
}
err = treee . Add ( leaf )
if err != nil {
  // Handle error
}

// Search
if found , err := treee . Search ( leaf . ID ); err == nil {
  // Do something with found Leaf
}

为了获得更好的性能，您应该将搜索请求放在不同的goroutines中（例如，请参见API/Handlers/Leaf.go文件中的GetLeaf()实现）。

为了进行调试或存储目的，您可能需要使用Treee索引上的PrintAll()方法将所有记录的叶子打印给作者（将其作为true作为美化印刷的JSON的参数，或为原始字符串false ）。

 // To print to Stdout
fmt . Println ( treee . PrintAll ( true ))

索引的持久性是通过使用插入时的自动保存以及使用Load()函数而不是在启动时使用New() Treee Intantiation实现的。

 treee , err := index . Load ( "path/to/treee.json" ) // If empty, will use "./saved/treee.json"

它可以使用相应的环境变量或命令行中的标志进行禁用，甚至可以通过编程方式进行禁用：

 treee . UsePersistence ( false ) // If you're positive you don't want it

可执行

您可以简单地构建可执行文件并启动Treee™索引引擎的实例。

$ git clone https://github.com/cyrildever/treee.git && cd treee && go build
$ ./treee -t.port 7001 -t.host localhost -t.init 101

 Usage of ./treee:
  -t.file string
        File path to an existing index
  -t.host string
        Host address (default "0.0.0.0")
  -t.init string
        Initial prime number to use for the index (default "0")
  -t.persist
        Activate persistence (default true)
  -t.port string
        HTTP port number (default "7000")

环境变量

如果设置，则以下环境变量将覆盖与命令行传递的任何相应的默认配置或标志：

HOST ：主机地址；
HTTP_PORT ：要使用的HTTP端口号；
INDEX_PATH ：以JSON格式的索引文件的路径；
INIT_PRIME ：初始质数（请注意，如果使用文件，它将没有任何效果，因为后者将占上风）；
USE_PERSISTENCE ：设置false以禁用将索引保存到文件中的使用。

API

/api组下面可用以下端点：

DELETE /leaf

此端点从索引中删除了传递的项目。

它期望一系列ID作为ids查询参数，例如。

 DELETE /api/leaf?ids=1235467890abcdef [ ... ] &ids=fedcba0987654321 [ ... ]
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)
Host: treee.io
Accept-Language: fr-FR
Accept-Encoding: gzip, deflate
Accept: application/json

如果删除了所有经过的项目，它将返回204状态代码，或200状态代码以及以下未删除ID的JSON列表，如果某些未删除：

{
  "ids" : [ " fedcba0987654321[...] " ]
}

GET /leaf

此端点根据传递的ID搜索项目。

它期望将一系列ID作为ids查询参数和可选的takeLast boolean（默认为false ），例如。 http://localhost:7000/api/leaf?ids=1234567890abcdef[...]&ids=fedcba0987654321[...]&takeLast=true

它返回状态代码200以及尊重以下格式的JSON对象：

[
  {
    "id" : " 1234567890abcdef[...] " ,
    "position" : 0 ,
    "size" : 100 ,
    "origin" : " 1234567890abcdef[...] " ,
    "previous" : " 1234567890abcdef[...] " ,
    "next" : " "
  },
  [ ... ]
]

如果找不到任何项目，它将返回带有空白的404状态代码。

GET /line

该端点返回同一子链/行中的所有ID。

它希望行的任何ID作为id查询参数，例如。 http://localhost:7000/api/line?id=1234567890abcdef[...]

它返回一个状态代码200长，以下JSON排序的ID数组（索引0为origin）：

[
  " 1234567890abcdef[...] " ,
  " fedcba0987654321[...] "
]

如果找不到任何项目，它将返回带有空白的404状态代码。

POST /leaf

此端点将项目添加到索引中。

它预计以下JSON对象是身体，前三个字段是强制性的：

{
  "id" : " <The item ID as a hash string representation> " ,
  "position" : 0 ,
  "size" : 100 ,
  "previous" : " <An optional item ID of the previous item in the current subchain if any> "
}

它返回状态代码和以下对象为JSON：

{
  "code" : 200 | 303 | 400 | 404 | 412 | 500,
  "result" : " <The inserted item ID if success> " ,
  "error" : " <The error message if failed> "
}

状态代码（及其含义）的列表如下：

200 ：插入的项目；
303 ：项目已经存在（由于文件应该是不可变的而未更新）；
400 ：错误参数（缺少项目，缺少强制性字段等）；
404 ：未找到以前的项目；
412 ：传递数据中的某些东西导致服务器失败（错误的JSON格式，...）;
500 ：服务器上发生了错误。

表演

平均而言，基本机器应该能够摄入超过1亿新记录，并每小时处理约50亿搜索查询。

例如，在Apple Macbook Pro 2.3 GHz Intel Core i9上，以16个GO DDR4 RAM为2400 MHz，我在使用101作为Init Prime时观察到以下表演：

插入：〜3亿（每小时1.2亿）中有10,000次添加；
搜索：约500ms的1,000,000个请求，即。大约2 MHz（每小时超过70亿）。在Apple Imac 3.1 GHz Intel Core i5上，16 GO DDR4 RAM在2667 MHz时也使用101作为Init Prime：
插入：〜240毫秒（每小时1.5亿）中增加了10,000次；
搜索：〜750ms的1,000,000个请求，即。大约1.3 MHz（每小时超过480亿）。