Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Further documentation updates.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 414ed6da4e175c29d4b27f893a3fd110fc4ca860
User & Date: dan 2012-11-13 20:16:00.788
Context
2012-11-14
18:23
Improvements to lsmusr.wiki. check-in: e47b5e3ae6 user: dan tags: trunk
2012-11-13
20:16
Further documentation updates. check-in: 414ed6da4e user: dan tags: trunk
18:44
Add lsmapi.wiki. And the script that generates it from lsm.h - tool/mklsmapi.tcl. check-in: 2377f4f991 user: dan tags: trunk
Changes
Side-by-Side Diff Ignore Whitespace Patch
Changes to tool/mklsmapi.tcl.
︙
180
181
182
183
184
185
186
187

188
189
190
191
192
193
194

180
181
182
183
184
185
186

187
188
189
190
191
192
193
194








-
+








close $fd

puts $document_preamble
puts "<h1>LSM API Topics</h1>"
puts <ol>
puts $document_toc
puts </ol>
set s "display:block;float:left;width:40ex"
set s "display:block;float:left;width:35ex"
puts "<h1 style=clear:both>All LSM API Functions</h1>"
foreach sym [lsort $document_functions] {
  puts "<span style=$s><a href=#$sym>$sym</a></span>"
}
puts "<br style=clear:both>"
puts "<h1 style=clear:both>All LSM API Types</h1>"
foreach sym [lsort $document_types] {
︙
Changes to www/lsmapi.wiki.
︙
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67






























68
69
70

71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112








































113
114
115
116
117
118
119

31
32
33
34
35
36
37






























38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

70
71
72








































73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119








-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+


-
+


-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+








<li><a href="#opening" style=text-decoration:none>Opening and Closing Database Cursors</a>
<li><a href="#positioning" style=text-decoration:none>Positioning Database Cursors</a>
<li><a href="#extracting" style=text-decoration:none>Extracting Data From Database Cursors</a>
<li><a href="#change" style=text-decoration:none>Change these!!</a>

</ol>
<h1 style=clear:both>All LSM API Functions</h1>
<span style=display:block;float:left;width:40ex><a href=#lsm_begin>lsm_begin</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_checkpoint>lsm_checkpoint</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_ckpt_size>lsm_ckpt_size</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_close>lsm_close</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_commit>lsm_commit</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_config>lsm_config</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_config_log>lsm_config_log</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_config_work_hook>lsm_config_work_hook</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_close>lsm_csr_close</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_cmp>lsm_csr_cmp</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_first>lsm_csr_first</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_key>lsm_csr_key</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_last>lsm_csr_last</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_next>lsm_csr_next</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_open>lsm_csr_open</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_prev>lsm_csr_prev</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_seek>lsm_csr_seek</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_valid>lsm_csr_valid</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_csr_value>lsm_csr_value</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_delete>lsm_delete</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_delete_range>lsm_delete_range</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_flush>lsm_flush</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_free>lsm_free</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_info>lsm_info</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_insert>lsm_insert</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_new>lsm_new</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_open>lsm_open</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_rollback>lsm_rollback</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_tree_size>lsm_tree_size</a></span>
<span style=display:block;float:left;width:40ex><a href=#lsm_work>lsm_work</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_begin>lsm_begin</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_checkpoint>lsm_checkpoint</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_ckpt_size>lsm_ckpt_size</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_close>lsm_close</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_commit>lsm_commit</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_config>lsm_config</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_config_log>lsm_config_log</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_config_work_hook>lsm_config_work_hook</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_close>lsm_csr_close</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_cmp>lsm_csr_cmp</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_first>lsm_csr_first</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_key>lsm_csr_key</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_last>lsm_csr_last</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_next>lsm_csr_next</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_open>lsm_csr_open</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_prev>lsm_csr_prev</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_seek>lsm_csr_seek</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_valid>lsm_csr_valid</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_csr_value>lsm_csr_value</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_delete>lsm_delete</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_delete_range>lsm_delete_range</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_flush>lsm_flush</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_free>lsm_free</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_info>lsm_info</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_insert>lsm_insert</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_new>lsm_new</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_open>lsm_open</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_rollback>lsm_rollback</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_tree_size>lsm_tree_size</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_work>lsm_work</a></span>
<br style=clear:both>
<h1 style=clear:both>All LSM API Types</h1>
<span style=display:block;float:left;width:40ex><a href=#lsm_compress>lsm_compress</a></span>
<span style=display:block;float:left;width:35ex><a href=#lsm_compress>lsm_compress</a></span>
<br style=clear:both>
<h1>All LSM API Constants</h1>
<span style=display:block;float:left;width:40ex><a href=#LSM_BUSY>LSM_BUSY</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CANTOPEN>LSM_CANTOPEN</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_AUTOCHECKPOINT>LSM_CONFIG_AUTOCHECKPOINT</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_AUTOWORK>LSM_CONFIG_AUTOWORK</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_BLOCK_SIZE>LSM_CONFIG_BLOCK_SIZE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_GET_COMPRESSION>LSM_CONFIG_GET_COMPRESSION</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_LOG_SIZE>LSM_CONFIG_LOG_SIZE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_MAX_FREELIST>LSM_CONFIG_MAX_FREELIST</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_MMAP>LSM_CONFIG_MMAP</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_MULTIPLE_PROCESSES>LSM_CONFIG_MULTIPLE_PROCESSES</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_NMERGE>LSM_CONFIG_NMERGE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_PAGE_SIZE>LSM_CONFIG_PAGE_SIZE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_SAFETY>LSM_CONFIG_SAFETY</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_SET_COMPRESSION>LSM_CONFIG_SET_COMPRESSION</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_USE_LOG>LSM_CONFIG_USE_LOG</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CONFIG_WRITE_BUFFER>LSM_CONFIG_WRITE_BUFFER</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_CORRUPT>LSM_CORRUPT</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_ERROR>LSM_ERROR</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_FULL>LSM_FULL</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_INFO_ARRAY_PAGES>LSM_INFO_ARRAY_PAGES</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_INFO_ARRAY_STRUCTURE>LSM_INFO_ARRAY_STRUCTURE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_INFO_DB_STRUCTURE>LSM_INFO_DB_STRUCTURE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_INFO_FREELIST>LSM_INFO_FREELIST</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_INFO_LOG_STRUCTURE>LSM_INFO_LOG_STRUCTURE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_INFO_NREAD>LSM_INFO_NREAD</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_INFO_NWRITE>LSM_INFO_NWRITE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_INFO_PAGE_ASCII_DUMP>LSM_INFO_PAGE_ASCII_DUMP</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_INFO_PAGE_HEX_DUMP>LSM_INFO_PAGE_HEX_DUMP</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_IOERR>LSM_IOERR</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_MISUSE>LSM_MISUSE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_NOMEM>LSM_NOMEM</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_OK>LSM_OK</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_PROTOCOL>LSM_PROTOCOL</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_SAFETY_FULL>LSM_SAFETY_FULL</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_SAFETY_NORMAL>LSM_SAFETY_NORMAL</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_SAFETY_OFF>LSM_SAFETY_OFF</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_SEEK_EQ>LSM_SEEK_EQ</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_SEEK_GE>LSM_SEEK_GE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_SEEK_LE>LSM_SEEK_LE</a></span>
<span style=display:block;float:left;width:40ex><a href=#LSM_SEEK_LEFAST>LSM_SEEK_LEFAST</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_BUSY>LSM_BUSY</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CANTOPEN>LSM_CANTOPEN</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_AUTOCHECKPOINT>LSM_CONFIG_AUTOCHECKPOINT</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_AUTOWORK>LSM_CONFIG_AUTOWORK</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_BLOCK_SIZE>LSM_CONFIG_BLOCK_SIZE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_GET_COMPRESSION>LSM_CONFIG_GET_COMPRESSION</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_LOG_SIZE>LSM_CONFIG_LOG_SIZE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_MAX_FREELIST>LSM_CONFIG_MAX_FREELIST</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_MMAP>LSM_CONFIG_MMAP</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_MULTIPLE_PROCESSES>LSM_CONFIG_MULTIPLE_PROCESSES</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_NMERGE>LSM_CONFIG_NMERGE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_PAGE_SIZE>LSM_CONFIG_PAGE_SIZE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_SAFETY>LSM_CONFIG_SAFETY</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_SET_COMPRESSION>LSM_CONFIG_SET_COMPRESSION</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_USE_LOG>LSM_CONFIG_USE_LOG</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CONFIG_WRITE_BUFFER>LSM_CONFIG_WRITE_BUFFER</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_CORRUPT>LSM_CORRUPT</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_ERROR>LSM_ERROR</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_FULL>LSM_FULL</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_INFO_ARRAY_PAGES>LSM_INFO_ARRAY_PAGES</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_INFO_ARRAY_STRUCTURE>LSM_INFO_ARRAY_STRUCTURE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_INFO_DB_STRUCTURE>LSM_INFO_DB_STRUCTURE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_INFO_FREELIST>LSM_INFO_FREELIST</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_INFO_LOG_STRUCTURE>LSM_INFO_LOG_STRUCTURE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_INFO_NREAD>LSM_INFO_NREAD</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_INFO_NWRITE>LSM_INFO_NWRITE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_INFO_PAGE_ASCII_DUMP>LSM_INFO_PAGE_ASCII_DUMP</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_INFO_PAGE_HEX_DUMP>LSM_INFO_PAGE_HEX_DUMP</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_IOERR>LSM_IOERR</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_MISUSE>LSM_MISUSE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_NOMEM>LSM_NOMEM</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_OK>LSM_OK</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_PROTOCOL>LSM_PROTOCOL</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_SAFETY_FULL>LSM_SAFETY_FULL</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_SAFETY_NORMAL>LSM_SAFETY_NORMAL</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_SAFETY_OFF>LSM_SAFETY_OFF</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_SEEK_EQ>LSM_SEEK_EQ</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_SEEK_GE>LSM_SEEK_GE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_SEEK_LE>LSM_SEEK_LE</a></span>
<span style=display:block;float:left;width:35ex><a href=#LSM_SEEK_LEFAST>LSM_SEEK_LEFAST</a></span>
<br style=clear:both>
<h2 id=lsm>LSM Error Codes<a id=LSM_OK></a><a id=LSM_ERROR></a><a id=LSM_BUSY></a><a id=LSM_NOMEM></a><a id=LSM_IOERR></a><a id=LSM_CORRUPT></a><a id=LSM_FULL></a><a id=LSM_CANTOPEN></a><a id=LSM_PROTOCOL></a><a id=LSM_MISUSE></a></h2>
<verbatim>#define LSM_OK         0
#define LSM_ERROR      1
#define LSM_BUSY       5
#define LSM_NOMEM      7
#define LSM_IOERR     10
︙
Changes to www/lsmusr.wiki.
︙
69
70
71
72
73
74
75
















76
77
78







































79
80
81
82
83
84
85

69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91



92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137








+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+








it is perhaps more accurate to say that an LSM database is stored on disk
in a single database file and a single (optional) log file.

<p>If required, it is possible to configure LSM to use external data
compression and/or encryption functions to transform data before it is
stored in the database file.

<p>Many database systems that support range queries, including <a
href=http://www.sqlite.org>SQLite 3</a>, Berkeley DB and Kyoto Cabinet, are
based on a <a href="http://en.wikipedia.org/wiki/B-tree">b-tree data
structure</a> or variant thereof. A b-tree structure minimizes the number of
disk sectors that must be read from disk when searching the database for a
specific key. However, b-tree implementations usually suffer from poor write
localization - updating the contents of a b-tree often involves modifying the
contents of nodes scattered throughout the database file. If the database is
stored on a spinning disk (HDD), then the disk heads must be moved before
writing non-contiguous sector, which is extremely slow. If the database is
stored on solid state storage (SDD) a similar phenomena is encountered due 
to the large erase-block sizes. In general, writing to a series of contiguous
disk sectors is orders of magnitude faster than updating to the same number
of disk sectors scattered randomly throughout a large file. Additionally,
b-tree structures are prone to fragmentation, reducing the speed of range
queries.
<p><i>Say something about the difference in performance characteristics 
between a b-tree and whatever it is LSM is. Link the performance graphs page.
</i>

<p><i>Todo: Should have references for the claims above.</i>

<p><i>Also, fix the link in the next paragraph to point to something more
specific.</i>

<p>LSM uses a <a href=lsm.wiki>different data structure</a> that makes the
following performance tradeoffs relative to a b-tree:

<ul>
  <li> A very large percentage of the disk sectors modified are contiguous.
       Additionally, in many cases the total number of sectors written
       to disk is reduced. This makes writing to an LSM database much
       faster than the equivalent b-tree.

  <li> LSM databases do not suffer from fragmentation to the same degree
       as b-trees. This means that the performance of large range queries 
       does not degrade as the database is updated as it may with a b-tree.

  <li> It is accepted that under some circumstances searching an LSM 
       database for a given key will involve examining more disk sectors
       than it would with a b-tree. In this sense both b-trees and LSM
       provide O(log(N)) efficiency, but the base of the logarithm is 
       generally larger for a b-tree than for LSM.
</ul>

<p>In other words, all things considered equal, writing to an LSM database
should be very fast and scanning through large ranges of keys should also
perform well, but searching the database for specific keys may be slightly
slower than when using a b-tree based system. Additionally, avoiding random
writes in favour of largely contiguous updates can significantly reduce the
wear on SSD or flash memory devices.

<p>Although it has quite different features to LSM in other respects, 
LevelDB makes similar performance tradeoffs.

<p>Benchmark test results for LSM are available here. <i>Todo: Link to a page
with performance graphs here</i>


<h1 id=using_lsm_in_applications>2. Using LSM in Applications </h1>

<p>LSM is not currently built or distributed independently. Instead, it
is part of the SQLite4 library. To use LSM in an application, the application
links against libsqlite4 and includes the header file "lsm.h" in any files
that access the LSM API.
︙