SQLite 的 HC-tree 計畫

Hacker News 首頁上看到的新計畫:「HC-tree is an experimental high-concurrency database back end for SQLite (sqlite.org)」,SQLite 弄了一個實驗性質的 backend,叫做 HC-tree

The HC-tree (hctree) project is an attempt to develop a new database backend that improves upon regular SQLite as follows:

他列了幾個重點,其中「Improved concurrency」這點題到了可以讓多個 writer 同時寫入運作,這點算是 SQLite 很大的改變,目前希望可以做到在 single-threaded 情況下不輸現有的 SQLite:

An implicit goal is that hctree must be as fast or faster than stock SQLite for all single-threaded cases. There is no point in running dozens of concurrent writers if each of them is an order of magnitude slower than a single writer writing to a legacy database.

另外一方面,這算是 SQLite 真正要面對資料庫的 isolation 的問題了,比起現在的版本,同時間從只有一個 writer 的架構要變成支援多個 writer 的架構,所以在「Concurrency Model」這邊也帶了一下他預期可以做到的事情。

然後這邊可以看到在解釋裡面有提到 table 與 index 還是 b-tree,這樣應該可以猜測 hctree 的實做方式應該還是在市場上已經很成熟的 MVCC 那套方法:

If no other client has modified any b-tree (table or index) entry or range that the transaction being committed accessed by a range or stabbing query, then the transaction is valid.

另外一個蠻大的改變是「Support for replication」,現有的 SQLite 可以透過 extension 的方式加掛支援 replication 功能,現在則是讓底層的 backend 直接支援。

底層支援新的 backend 以後看起來會有不少變化可以玩,第一個想到的當然是變成 server 類型的服務,也就是像 MySQL 或是 PostgreSQL 這樣的方式,另外一種方向是包裝成 distributed database,讓應用程式可以簡單跨機器使用。

目前還不知道會往什麼方向走就是了,也有可能 SQLite 這邊只實做 backend,上面讓大家發揮...

PostgreSQL 裡的 B-tree 結構

在「Indexes in PostgreSQL — 4 (Btree)」這邊看到講 PostgreSQLB-tree 結構以及常見的查詢會怎麼使用 B-tree。

裡面講了三種查詢,第一種是等號的查詢 (Search by equality),第二種是不等號的查詢 (Search by inequality),第三種是範圍的查詢 (Search by range)。再後面講到排序與 index 的用法。

雖然是分析 PostgreSQL,但裡面是一般性的概念,其他使用 B-tree 結構的資料庫也是類似作法...