{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:06:03Z","timestamp":1778295963475,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540544142","type":"print"},{"value":"9783540476153","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54414-3_38","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:44:26Z","timestamp":1330209866000},"page":"181-206","source":"Crossref","is-referenced-by-count":8,"title":["Grow and post index trees: Role, techniques and future potential"],"prefix":"10.1007","author":[{"given":"David B.","family":"Lomet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"issue":"2","key":"12_CR1","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1109\/69.87964","volume":"1","author":"R. Baez-Yates","year":"1989","unstructured":"Baez-Yates, R. and Larson, P. Performance of B+trees with partial expansions. IEEE Trans. on Knowledge and Data Engineering 1,2 (June 1989) 248\u2013257.","journal-title":"IEEE Trans. on Knowledge and Data Engineering"},{"issue":"3","key":"12_CR2","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R. and McCreight, E. Organization and maintenance of large ordered indices. Acta Inf. 1,3(1972), 173\u2013189.","journal-title":"Acta Inf."},{"issue":"1","key":"12_CR3","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/320521.320530","volume":"2","author":"R. Bayer","year":"1977","unstructured":"Bayer, R. and Unterauer, K. Prefix B-trees. ACM Trans. on Database Systems 2,1 (Mar. 1977), 11\u201326.","journal-title":"ACM Trans. on Database Systems"},{"issue":"9","key":"12_CR4","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J. Bentley","year":"1975","unstructured":"Bentley, J. Multidimensional binary search trees for associative searching. Comm. ACM 18,9(Sept. 1975) 509\u2013517.","journal-title":"Comm. ACM"},{"key":"12_CR5","volume-title":"Writing efficient programs","author":"J. Bentley","year":"1982","unstructured":"Bentley, J. Writing efficient programs. Prentice Hall, Englewood Cliffs, NJ (1982)"},{"issue":"2","key":"12_CR6","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. Carter","year":"1979","unstructured":"Carter, J. and Wegman, M. Universal classes of hash functions. J. Computer and System Sciences 18,2 (April 1979) 143\u2013154.","journal-title":"J. Computer and System Sciences"},{"issue":"2","key":"12_CR7","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"Comer, D. The ubiquitous B-tree. ACM Comp. Surv. 11,2(June 1979), 121\u2013138.","journal-title":"ACM Comp. Surv."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"DeWitt, D., Katz, R., Olken, F., Shapiro, L., Stonebraker, M., and Wood, D. Implementation techniques for main memory database systems. Proc. ACM SIGMOD Conf. (Boston, Mass. 1984) 1\u20138.","DOI":"10.1145\/602259.602261"},{"issue":"3","key":"12_CR9","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/320083.320092","volume":"4","author":"R. Fagin","year":"1979","unstructured":"Fagin, R. Nievergelt, J., Pippenger, N. and Strong, R. Extendible hashing: a fast access method for dynamic files. ACM Trans. on Database Systems 4,3 (Sept. 1979) 315\u2013344.","journal-title":"ACM Trans. on Database Systems"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Faloutsos, C. Multiattribute hashing using gray codes. Proc. ACM SIGMOD Conf. (Washington, DC 1986) 227\u2013238.","DOI":"10.1145\/16894.16877"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Freeston, M. The BANG file: a new kind of grid file. Proc. ACM SIGMOD Conf. (San Francisco, Cal. 1987) 260\u2013269.","DOI":"10.1145\/38713.38743"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Guenther, O. The design of the cell tree: an object oriented index structure for geometric databases. Proc. IEEE Data Engineering Conf. (Los Angeles, Cal. 1989), 598\u2013605.","DOI":"10.1109\/ICDE.1989.47267"},{"issue":"4","key":"12_CR13","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/122058.122065","volume":"19","author":"O. Guenther","year":"1990","unstructured":"Guenther, O. and Buchmann, A. Research issues in spatial databases. SIGMOD Record 19,4 (Dec. 1990), 61\u201368.","journal-title":"SIGMOD Record"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Guttman, A. R-trees: a dynamic index structure for spatial searching, Proc. ACM SIGMOD Conf. (Boston, Mass. 1984)","DOI":"10.1145\/602259.602266"},{"key":"12_CR15","unstructured":"IBM, Introduction to IBM\/360 direct access storage devices and organization methods. C20-1649, IBM Corp.(White Plains, N.Y. 1966)"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Jagadish, H. Linear clustering of objects with multiple attributes. Proc. ACM SIGMOD Conf. (Atlantic City, N.J. 1990) 332\u2013342.","DOI":"10.1145\/93597.98742"},{"key":"12_CR17","unstructured":"Joshi, A. and Rodwell, K. A relational database management system for production applications. Digital Technical Journal no. 8 (Feb. 1989) 99\u2013109."},{"issue":"3","key":"12_CR18","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1147\/sj.133.0186","volume":"13","author":"D. Keehn","year":"1974","unstructured":"Keehn, D. and Lacy, J. VSAM data set design parameters. IBM Systems Journal 13,3 (1974) 186\u2013212.","journal-title":"IBM Systems Journal"},{"key":"12_CR19","volume-title":"The art of computer programming, Vol. 3: sorting and searching","author":"D. Knuth","year":"1973","unstructured":"Knuth, D. The art of computer programming, Vol. 3: sorting and searching. Addison-Wesley, Reading, Mass. (1973)"},{"issue":"1","key":"12_CR20","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1109\/MS.1984.233391","volume":"1","author":"B. Lampson","year":"1984","unstructured":"Lampson, B. Hints for computer system design. IEEE Software 1,1 (Jan. 1984) 11\u201328.","journal-title":"IEEE Software"},{"key":"12_CR21","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/BF01931695","volume":"18","author":"P. Larson","year":"1978","unstructured":"Larson, P. Dynamic hashing. BIT 18 (1978) 184\u2013201.","journal-title":"BIT"},{"key":"12_CR22","unstructured":"Larson, P. Linear hashing with partial expansions. Proc. VLDB Conf. (Montreal, Canada 1980), 224\u2013232."},{"issue":"4","key":"12_CR23","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1145\/319628.319663","volume":"6","author":"P. Lehman","year":"1981","unstructured":"Lehman, P. and Yao, S. Efficient locking for concurrent operations on B-trees. ACM Trans. on Database Systems 6,4 (Dec. 1981) 650\u2013670.","journal-title":"ACM Trans. on Database Systems"},{"key":"12_CR24","unstructured":"Litwin, W. Linear hashing: a new tool for file and table addressing. Proc. VLDB Conf. (Montreal, Canada 1980), 212\u2013223."},{"issue":"2","key":"12_CR25","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/MS.1987.230092","volume":"4","author":"W. Litwin","year":"1987","unstructured":"Litwin, W. and Lomet, D. A new method for fast data searches with keys. IEEE Software 4,2 (Mar. 1987), 16\u201324.","journal-title":"IEEE Software"},{"key":"12_CR26","unstructured":"Lomet, D. Digital B-trees. Proc. VLDB Conf. (Cannes, France 1981) 333\u2013344."},{"issue":"1","key":"12_CR27","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/12047.12049","volume":"12","author":"D. Lomet","year":"1987","unstructured":"Lomet, D. Partial expansions for file organizations with an index. ACM Trans. on Database Systems 12,1 (Mar. 1987), 65\u201384.","journal-title":"ACM Trans. on Database Systems"},{"issue":"4","key":"12_CR28","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1145\/49346.50067","volume":"13","author":"D. Lomet","year":"1988","unstructured":"Lomet, D. A simple bounded disorder file organization with good performance. ACM Trans. on Database Systems 13,4 (Dec. 1988) 525\u2013551.","journal-title":"ACM Trans. on Database Systems"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Lomet, D. and Salzberg, B. Access methods for multiversion data. Proc. ACM SIGMOD Conf. (Portland, Ore. 1989) 315\u2013324.","DOI":"10.1145\/67544.66956"},{"issue":"4","key":"12_CR30","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1145\/99935.99949","volume":"15","author":"D. Lomet","year":"1990","unstructured":"Lomet, D. and Salzberg, B. The hB-tree: a multiattribute indexing method with good guaranteed performance. ACM Trans. on Database Systems 15,4 (Dec. 1990) 625\u2013658.","journal-title":"ACM Trans. on Database Systems"},{"key":"12_CR31","series-title":"Technical Report","volume-title":"Concurrency and recovery for index trees","author":"D. Lomet","year":"1991","unstructured":"Lomet, D. and Salzberg, B. Concurrency and recovery for index trees. Digital Equipment Corp. Technical Report, Cambridge Research Lab, Cambridge, Mass. (to appear, summer, 1991)"},{"key":"12_CR32","unstructured":"Lynch, C. and Stonebraker, M. Extended user-defined indexing with application to textual databases. Proc. VLDB Conf. (Los Angeles, Cal. 1988) 306\u2013317."},{"issue":"2","key":"12_CR33","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1147\/sj.162.0096","volume":"16","author":"W. McGee","year":"1977","unstructured":"McGee, W. The information management system IMS\/VS; part II: data base facilities. IBM Systems Journal 16,2 (1977) 96\u2013122.","journal-title":"IBM Systems Journal"},{"key":"12_CR34","unstructured":"Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H., and Schwarz, P. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. IBM Research Report RJ 6649, IBM Almaden Research Center (Jan. 1989) and ACM Trans. on Database Systems (to appear)."},{"key":"12_CR35","unstructured":"Mohan, C. and Levine, F. ARIES\/IM: an efficient and high concurrency index management method using write ahead logging. IBM Research Report RJ6846, IBM Almaden Research Center (August 1989)."},{"key":"12_CR36","doi-asserted-by":"crossref","unstructured":"Orenstein, J. and Merrett, T. A class of data structures for associative searching. Proc. ACM PODS Conf. (Waterloo, Canada, 1984) 181\u2013190.","DOI":"10.1145\/588011.588037"},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"Ramakrishna, M. and Mukhopadhyay, P. Analysis of bounded disorder file organization. Proc. ACM PODS Conf. (San Francisco, Cal. 1988) 117\u2013125.","DOI":"10.1145\/308386.308424"},{"key":"12_CR38","doi-asserted-by":"crossref","unstructured":"Sagiv, Y. Concurrent operations on B-trees with overtaking. Proc. ACM PODS Conf. (Portland, Ore., 1985) 28\u201337.","DOI":"10.1145\/325405.325409"},{"key":"12_CR39","volume-title":"File structures: an analytic approach","author":"B. Salzberg","year":"1988","unstructured":"Salzberg, B. File structures: an analytic approach. Prentice Hall, Englewood Cliffs, NJ (1988)"},{"key":"12_CR40","doi-asserted-by":"crossref","unstructured":"Salzberg, B. Practical spatial database access methods. Proc. Symposium on Applied Computing (Kansas City, Kan. 1991) 82\u201390.","DOI":"10.1109\/SOAC.1991.143852"},{"key":"12_CR41","unstructured":"Sellis, T., Roussopoulos, N., and Faloutsos, C. The R+-tree: a dynamic index for multi-dimensional objects. Proc. VLDB Conf. (Brighton, England 1987)"},{"key":"12_CR42","doi-asserted-by":"crossref","unstructured":"Srinivasan, V. and Carey, M. Performance of B-tree concurrency control algorithms. Proc. ACM SIGMOD Conf. (Denver, Col. 1991) 416\u2013425.","DOI":"10.1145\/115790.115860"}],"container-title":["Lecture Notes in Computer Science","Advances in Spatial Databases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54414-3_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:21:22Z","timestamp":1619572882000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54414-3_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540544142","9783540476153"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/3-540-54414-3_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}