模板
教程
環境
性能
功能
管理
Sqlite中文排序研究
SqliteMILY: 宋體">是一個用C語言實現的小型SQL數據庫引擎。它體積小巧但功能強大，對硬件資源要求很低而且性能表現卓越，非常適合于嵌入式應用環境。最近發現sqlite并不支持中文(拼音/筆畫)排序，而這個功能又是我們必需的，所以花了些時間去研究。我對Sqlite的了解只能算是業余級，在研究的過程或許走了些彎路，或許已經有現存的算法可利用，不管怎么樣，在研究過程中還是有不少收獲，寫出來和大家探討一下。
我們知道，計算機中的每一個字符都有一個內碼。在默認情況下，計算機排序時，比較兩個字符的大小就是比較字符內碼的大小，這對于英文來說沒有問題，因為英文字母的內碼是按字母順序遞增的。對于中文來說，就比較麻煩了：首先，中文的排序方式有多種，比如按內碼排序、按拼音排序和按筆畫排序，要通過參數指定排序的方式，否則計算機就按內碼排序了。其次，漢字的內碼順序即不同于拼音順序，也不同于按筆畫順序。在GB2312編碼中，漢字基本上按拼音排序（據說有例外，不太清楚）。在GBK中，它在GB2312基礎上進行了擴充，兼容GB2312中的所有字符，所以不是按拼音排序了。在Unicode中，漢字的排列似乎更沒有什么規律可言了。
為了解決內碼順序與用戶習慣順序(如拼音順序)的沖突，在glibc的locale數據里，要求提供排序方式(collate)的描述。我看了一下glibc-2.3.5提供的locale數據，在簡體中文(zh_CN)的locale數據描述里，關于排序方式的描述如下：
% ISO 14651 collation sequence
LC_COLLATE
copy "iso14651_t1"
END LC_COLLATE
也就是說，照抄iso14651_t1的排序方式。打開iso14651_t1文件看了一下，也沒有發現關于中文的特殊處理，可以推斷glibc默認的排序方式就是按unicode排序。
所以不能指望glibc提供中文排序功能，如果SQLite支持了中文排序只能是做了特殊處理。瀏覽了一下SQLite的代碼，這種希望似乎也不大。在網上也沒有查到相關的資料和補丁，看來只能靠自己了。
不過，在瀏覽SQLite代碼時還是有些收獲，至少知道了它比較數據記錄的過程：
1. sqlite3VdbeExec調用sqlite3BtreeInsert把記錄插入到適當的位置。
2. sqlite3BtreeInsert調用sqlite3BtreeMoveto找到要插入的位置。
3. sqlite3BtreeMoveto調用sqlite3VdbeRecordCompare比較兩條記錄的大小。
4. sqlite3VdbeRecordCompare調用sqlite3MemCompare比較字段的大小。
5. sqlite3MemCompare調用binCollFunc去做真正的比較。
6. binCollFunc是一個回調函數，由外層設置的。
進一步研究，知道了binCollFunc的來源：
1. struct CollSeq是一個用來比較的對象，它帶有一個比較函數和相關上下文。
2. 通過multiSelectCollSeq找到合適的CollSeq對象。
3. multiSelectCollSeq調用sqlite3ExprCollSeq查找。
4. multiSelectCollSeq調用sqlite3CheckCollSeq查找。
5. 查找標準是SELECT或CREATE TABLE所帶的COLLATE子句。
6. 也就是說可以通過SELECT或CREATE TABLE的參數來決定選擇哪個比較函數。
基于上面這些認識，我們知道比較函數是可以指定的了。接下來的問題是，我們能否自定義比較函數，如何自定義，以及如何安裝到SQLite里。很快發現SQLite已經提供了安裝比較函數的接口:
|
int sqlite3_create_collation16(
sqlite3* db,
const char *zName,
int enc,
void* pCtx,
int(*xCompare)(void*,int,const void*,int,const void*)
)
int sqlite3_create_collation(
sqlite3* db,
const char *zName,
int enc,
void* pCtx,
int(*xCompare)(void*,int,const void*,int,const void*)
)
|
前者用來安裝UTF-16的比較函數，后者用來安裝UTF-8的比較函數。我們發現，在main.c里已經安裝了一些內置的比較函數：
|
sqlite3_create_collation(db, "BINARY", SQLITE_UTF8, 0,binCollFunc);
sqlite3_create_collation(db, "BINARY", SQLITE_UTF16, 0,binCollFunc);
sqlite3_create_collation(db, "NOCASE", SQLITE_UTF8, 0, nocaseCollatingFunc); |
好了，原理清楚了，我們要做的只是提供一個比較函數，并且安裝進去就OK了。為了測試，我寫一個按拼音排序的比較函數(按筆畫排序類似):
|
int pinyin_cmp(
void *NotUsed,
int nKey1, const void *pKey1,
int nKey2, const void *pKey2)
{
int n = nKey1 < nKey1 ? nKey1 : nKey2;
return pinyin_strncmp(pKey1, pKey2, n + 1);
} |
安裝比較函數時要注意，因為我們實現的比較函數是針對UTF-16的，所以名字要用UTF-16編碼。但是由于linux下默認的wchar_t是32位的，不能直接用L”pinyin”的方式把ANSI字符串轉換成UTF-16字符串，只能按下列方式。
|
unsigned short zName[] = {'p', 'i', 'n', 'y', 'i', 'n', 0};
sqlite3_create_collation16(db, zName, SQLITE_UTF16, 16, pinyin_cmp); |
測試結果正常(紅色部分為按拼音排序，藍色部分為默認排序):
|
sqlite> create table person(name text, age int); sqlite> insert into person values("張三", 23); sqlite> insert into person values("張三豐", 23); sqlite> insert into person values("李四", 24); sqlite> insert into person values("李四叔", 24); sqlite> insert into person values("王五", 25); sqlite> insert into person values("王五妹", 25); sqlite> insert into person values("趙七", 26); sqlite> insert into person values("趙七姑", 26); sqlite> sqlite> select * from person order by name collate pinyin;
李四|24
李四叔|24
王五|25
王五妹|25
張三|23
張三豐|23
趙七|26
趙七姑|26 sqlite> select * from person order by name;
張三|23
張三豐|23
李四|24
李四叔|24
王五|25
王五妹|25
趙七|26
趙七姑|26 |
總結：SQLite的架構設計非常優秀，接口定義得也比較合理，支持中文排序變得非常簡單。
