22:
141:
that is sufficient to capture the application-specific aspects of a wide variety of index designs. The GiST infrastructure code manages the layout of the index pages on disk, the algorithms for searching indexes and deleting from indexes, and complex transactional details such as page-level locking
185:
The
PostgreSQL GiST implementation includes support for variable length keys, composite keys, concurrency control and recovery; these features are inherited by all GiST extensions. There are several contributed modules developed using GiST and distributed with PostgreSQL. For example:
146:
for crash recovery. This allows authors of new tree-based indexes to focus on implementing the novel features of the new index type — for example, the way in which subsets of the data should be described for search — without becoming experts in database system internals.
98:, providing a concurrent and recoverable height-balanced search tree infrastructure without making any assumptions about the type of data being stored, or the queries being serviced. GiST can be used to easily implement a range of well-known indexes, including
137:
in the context of database systems: it allows the easy evolution of a database system to support new tree-based indexes. It achieves this by factoring out its core system infrastructure from a narrow
114:, and many others; it also allows for easy development of specialized indexes for new data types. It cannot be used directly to implement non-height-balanced trees such as
130:. Not only is it extensible in terms of data type support and tree layout, it allows the extension writer to support any query predicates that they choose.
111:
107:
65:
43:
36:
328:
269:, Proc. 11th Int'l Conf. on Scientific and Statistical Database Management, Cleveland, OH, July 1999, 122–133.
214:
313:
199:
ltree - data types, indexed access methods and queries for data organized as a tree-like structures
30:
295:
266:
151:
289:
47:
230:
91:
150:
Although originally designed for answering
Boolean selection queries, GiST can also support
267:
How to Avoid
Building DataBlades That Know the Value of Everything and the Cost of Nothing
8:
333:
234:
170:
143:
262:, Proc. 24th Int'l Conf. on Very Large Data Bases, Edinburgh, Scotland, September 1999.
126:. GiST can be used for any data type that can be naturally ordered into a hierarchy of
252:
245:
123:
241:. Proc. 21st Int'l Conf. on Very Large Data Bases, Zürich, September 1995, 562–573.
238:
284:
218:
83:
259:
255:. Proc. 14th Int'l Conf. on Data Engineering, Orlando, FL, Feb. 1998, 380–389.
322:
155:
134:
248:. Proc. ACM SIGMOD Conf. on Management of Data, Tucson, AZ, May 1997, 62–72.
209:
The
PostgreSQL GiST implementation provides the indexing support for the
122:(tries), though like prefix trees it does support compression, including
167:
303:
174:
127:
115:
99:
95:
308:
210:
196:
tsearch2 - a searchable (full text) data type with indexed access
190:
rtree_gist, btree_gist - GiST implementation of R-tree and B-tree
279:
103:
193:
intarray - index support for one-dimensional array of int4's
119:
138:
87:
177:
Universal Server, and as a standalone library, libgist.
244:
Marcel
Kornacker, C. Mohan and Joseph M. Hellerstein.
205:
cube - data type, representing multidimensional cubes
246:
Concurrency and
Recovery in Generalized Search Trees
166:The most widely used GiST implementation is in the
90:that can be used to build a variety of disk-based
253:Generalizing "Search" in Generalized Search Trees
320:
239:Generalized Search Trees for Database Systems
296:Developing PostgreSQL extension with GiST
260:High-Performance Generalized Search Trees
66:Learn how and when to remove this message
29:This article includes a list of general
202:hstore - a storage for (key,value) data
321:
15:
154:, and various forms of statistical
94:. GiST is a generalization of the
13:
292:for the GiST support in PostgreSQL
161:
35:it lacks sufficient corresponding
14:
345:
273:
173:; it was also implemented in the
82:or Generalized Search Tree, is a
20:
133:GiST is an example of software
1:
280:GiST research project website
224:
215:geographic information system
180:
7:
285:PostgreSQL GiST Development
10:
350:
142:for high concurrency and
329:Trees (data structures)
304:GiST in PostgreSQL wiki
152:nearest-neighbor search
50:more precise citations.
217:) and the BioPostgres
158:over large data sets.
231:Joseph M. Hellerstein
235:Jeffrey F. Naughton
171:relational database
144:write-ahead logging
258:Marcel Kornacker.
237:and Avi Pfeffer.
124:lossy compression
76:
75:
68:
341:
300:
71:
64:
60:
57:
51:
46:this article by
37:inline citations
24:
23:
16:
349:
348:
344:
343:
342:
340:
339:
338:
319:
318:
298:
276:
227:
183:
164:
162:Implementations
72:
61:
55:
52:
42:Please help to
41:
25:
21:
12:
11:
5:
347:
337:
336:
331:
317:
316:
311:
306:
301:
293:
287:
282:
275:
274:External links
272:
271:
270:
265:Paul M. Aoki.
263:
256:
251:Paul M. Aoki.
249:
242:
226:
223:
219:bioinformatics
207:
206:
203:
200:
197:
194:
191:
182:
179:
163:
160:
84:data structure
78:In computing,
74:
73:
28:
26:
19:
9:
6:
4:
3:
2:
346:
335:
332:
330:
327:
326:
324:
315:
312:
310:
307:
305:
302:
297:
294:
291:
290:Documentation
288:
286:
283:
281:
278:
277:
268:
264:
261:
257:
254:
250:
247:
243:
240:
236:
232:
229:
228:
222:
220:
216:
212:
204:
201:
198:
195:
192:
189:
188:
187:
178:
176:
172:
169:
159:
157:
156:approximation
153:
148:
145:
140:
136:
135:extensibility
131:
129:
125:
121:
117:
113:
109:
105:
101:
97:
93:
89:
85:
81:
70:
67:
59:
49:
45:
39:
38:
32:
27:
18:
17:
299:(in Russian)
208:
184:
165:
149:
132:
120:prefix trees
92:search trees
79:
77:
62:
53:
34:
314:BioPostgres
48:introducing
334:PostgreSQL
323:Categories
225:References
181:PostgreSQL
168:PostgreSQL
116:quad trees
31:references
128:supersets
56:June 2015
221:system.
175:Informix
112:RD-trees
108:hB-trees
100:B+ trees
309:PostGIS
211:PostGIS
104:R-trees
96:B+ tree
44:improve
33:, but
86:and
80:GiST
139:API
118:or
88:API
325::
233:,
110:,
106:,
102:,
213:(
69:)
63:(
58:)
54:(
40:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.