Эти алгоритмы разработаны на основе работы "Access Methods for Next-Generation Database Systems" by Marcel Kornaker (PDF.gz). Их модификация производилась в следующих целях:

1. приспособить исходные алгоритмя к соглашениям, принятым в PostgreSQL. В связи с этим заметно изменен алгоритм поиска. В постгресе, в отличие от идеальных условий, функция search вызывается несолько раз и она должна выдать следующий tuple при очередном вызове. Так же она не должна оставлять локов на страницах между вызовами.
2. приспособить алгоритмы к ограничениями, выявленными в реальной эксплуатации. Это коснулось ф-ции split, поскольку user-defined функция picksplit может быть не идеальна.
3. Однопроходность алгоритма в целях оптимизации.
4. Недостаток некоторых деталей в работе. Они были опущены как несущественные в теоретической работе.

Алгоритм поиска

gettuple находит tuple, соответсвующий поисковому предикату. Функция запоминает свое состояние и при следующем вызове возвращает следующий tuple. Элемент стека содержит страницу, ее LSN и LSN родительской страницы. Значение currentposition сохраняется между вызовами.

gettuple(search-pred)
	if ( firsttime )
		push(stack, [root, 0, 0]) // page, LSN, parentLSN
		currentposition=0
	end
	top = top of stack
	while(true)
		latch( top->page, S-mode )
		if ( top->page->lsn != top->lsn ) 
			top->lsn = top->page->lsn
			currentposition=0
			if ( top->parentlsn < top->page->nsn )
				add to stack rightlink
		else
			currentposition++
		end

		while(true)
			currentposition = find_first_match( currentposition )
			if ( currentposition is invalid )
				unlatch( top->page )
				pop stack
				top = top of stack
				break loop
			else if ( top->page is leaf )
				unlatch( top->page )
				return tuple
			else 
				add to stack child page
			end
			currentposition++
		end
	end

Однопроходный алгоритм вставки.

С помощью ф-ции findLeaf находиться ветвь дерева для вставки, далее происходит поуровневая вставка. При вставке на страницу залочена она и ее родительская страница. Ф-ции findParent и findPath предназначены для поиска родительских страниц, котороые могут измениться в условия конкурентного доступа. Ф-ция pageSplit является реккурентной и способна разбить страницу более чем на две страницы, что может быть необходимо в случае ключей с разной длиной или вставки более одного ключа. Пользовательская ф-ция pickSplit не способна в таком случае гарантировать наличие достаточного места на странице.

findLeaf(new-key)
	push(stack, [root, 0]) //page, LSN
	while(true)
		top = top of stack
		latch( top->page, S-mode )
		top->lsn = top->page->lsn
		if (  top->parent->lsn < top->page->nsn )
			unlatch( top->page )
			pop stack
		else if ( top->page is not leaf )
			push( stack, [get_best_child(top->page, new-key), 0] )
			unlatch( top->page )
		else
			unlatch( top->page )
			latch( top->page, X-mode )
			if ( top->page is not leaf )
				unlatch( top->page )
				pop stack
			else if ( top->parent->lsn < top->page->nsn )
				unlatch( top->page )
				pop stack
			else
				break loop
			end
		end
	end

findPath( stack item )
	push stack, [root, 0, 0] // page, LSN, parent 
	while( stack )
		top = top of stack
		latch( top->page, S-mode )
		if ( top->parent->page->lsn < top->page->nsn )
			push stack, [ top->page->rightlink, 0, top->parent ]
		end
		for( each tuple on page )
			if ( tuple->pagepointer == item->page )
				break loop
			else
				add to stack at the end [tuple->pagepointer, 0, top]
			end
		end
		unlatch( top->page )
		pop stack
	end
	
findParent( stack item )
	parent = item->parent
	latch( parent->page, X-mode )
	if ( parent->page->lsn != parent->lsn )
		while(true) 
			search parent tuple on parent->page, if found the return
			rightlink = parent->page->rightlink
			unlatch( parent->page )
			if ( rightlink is incorrect )
				break loop
			end
			parent->page = rightlink
			latch( parent->page, X-mode )
		end
		findPath( item->parent )
		replace part of stack to new one
		findParent( item )
	end

pageSplit(page, allkeys)
	(lkeys, rkeys) = pickSplit( allkeys )
	if ( page is root )
		lpage = new page
	else
		lpage = page
	rpage = new page
	if ( no space left on rpage )
		newkeys = pageSplit( rpage, rkeys )
	else
		push newkeys, union(rkeys)
	end
	if ( no space left on lpage )
		push newkeys, pageSplit( lpage, lkeys )
	else
		push newkeys, union(lkeys)
	end
	return newkeys


placetopage(page, keysarray)
	if ( no space left on page )
		keysarray = pageSplit(page, [ extract_keys(page), keysarray ])
		last page in chain gets old NSN,
		original and others - new NSN from current LSN
		if ( page is root )
			make new root with keysarray
		end
	else
		put keysarray on page
		if ( length of keysarray > 1 )
			keysarray = [ union(keysarray) ]
		end
	end
	
insert(new-key)
	findLeaf(new-key)
	keysarray = [new-key]
	top = top of stack
	while(true)
		findParent( top )
		keysarray = placetopage(top->page, keysarray)
		unlatch( top->page )
		pop stack;
		top = top of stack
		if (length of keysarray == 1)
			newboundingkey = union(oldboundingkey, keysarray)
			if (newboundingkey == oldboundingkey)
				unlatch top->page
				break loop
			end
		end
	end