Двоичное дерево строится на принципах:
1) дерево строится из элементов-узлов
2) у каждого элемента-узла может быть два под-узла (но не больше, поэтому дерево и называется двоичным
3) что меньше -- налево, что больше -- направо
*) Как следствие, в одном дереве не могут существовать два элемента с одинаковым значением (PRIMARY KEY)
Двоичное (иначе бинарное) дерево применяется для быстрого поиска. Если в дереве содержится N элементов, то в худшем случае поиск занимает N итераций, а в лучшем -- log2(N). Чтобы всегда иметь только лучшие показатели, дерево должно быть сбалансировано. Тут тебе нужно уяснить что такое красно-чёрные деревья.
Решение в лоб:
1) создаётся массив записей R[]
2) у записи выбирается ключевое поле (или набор полей) R.key
3) создатся массив индексов/номеров записей I[], только при движении по этому массиву от начального элемента до конечного должно соблюдатся правило R[I[i]].key < R[I[i+1]].key (можно использовать и не строгое неравенство, если допускается нексолько ключей с одинаковым значением)
4) При поиске, вставке, изменениии нужно быстро пробегать по массиву I[] методом половинного деления (поиск по двоичному дереву) и дальше по смыслу...
-- главный недостаток -- необходимо очень сильно двигать элементы массива I[] при изменении, добавлении, удалении ключа, это очень ресурсоёмкая операция.
В любом случае, без сбалансированного дерева нормальную БД построить нереально. (Хотя мир клином не сошёлся на бинароном дереве, есть ещё и троичные и под фибоначи и хэш и ...)