Как лучше организовать структуру БД, для организации модуля друзей на сайте?
ваш id, friend_id друга

1 2
2 1

если есть пара, то вы друзья, если нет, тоесть только 1 2 или 2 1, то ещё нет ждёте подтверждения.

Вот такой запрос, выдаёт список друзей:

SELECT login, friends.id AS check_id, friends.friend_id AS check_friend_id, 
(SELECT id FROM friends WHERE id=check_friend_id AND friend_id=check_id)AS checkout
FROM friends LEFT JOIN users ON (users.id=friends.friend_id)
WHERE friends.id=?i
HAVING checkout IS NOT NULL ORDER BY login

И два индекса на id, friend_id и наоборот friend_id, id

Есть вариант второй, делать только одну запись, но добавить поле friendship, а потом проверять её наличие и если есть, то апдейтить friendship=1. Надеюсь вам это поможет.
Сделайте табличку дружественных связей uid2uid и очередь (другая табличка или сторонний модуль) на внесение изменений в табличку связей. Главное, чтобы в очередь заявок сами заявки инсертились «со свистом» (INSERT DELAYED)…