rank (order) in database

현재 프로젝트에 적용하기 위한 ranking 로직으로는 GreenHopper 방식이 적합해보인다. lexoRank 가 좋은 것이긴하지만 너무 복잡하다. 드래그앤드랍 이동이 있으며 모든 관련 Row 를 업데이트 하고 싶지는 않다. 하지만 그래도 거의 무한대의 순서변경이 가능하도록 하기 위해서는 셋오프 값을 좀 크게 잡아주면 될 것이다. 100000000 으로 일억 정도 잡아주면 되지 않을까? 

새로 추가될 경우에는 일억, 이억, 삼억, ... 십억, 십일억, ....

100억 기준이 좋을 듯 보인다.

https://stackoverflow.com/questions/1848700/biggest-integer-that-can-be-stored-in-a-double

9007199254740992 (90071 / 99254740992) 그럴 경우 9만개 정도의 데이터들을 대략적으로 다룰 수 있어보인다.

중간으로 이동할 경우 그 사이값의 중간값. 또 중간으로 이동할 경우 그 중간값...

method 의 경우 다음과 같은 종류가 있으면 될 것 같다. 테이블 상의 필드 명칭은 rank.

 

1. Insert(x) - Insert record x into the table
2. Delete(x) - Delete record x from the table
3. Before(x,n) - Return the 'n' records preceding the record x in the sorted list.
4. After(x,n) - Return the 'n' records succeeding the record x in the sorted list.
5. First(n) - Return the first 'n' records from the sorted list.
6. Last(n) - Return the last 'n' records from the sorted list.
7. Compare(x,y) - Given two records x and y from the table, find if x > y.

 

 

가장 기본적인 동작 구현 방식. sigle ups and downs 는 범용성이 없어서 패쓰. Drag-and-drop move 부분도 다수의 rows 를 업데이트해야 하므로 패쓰.

 

 

Limiting moves to single ups and downs makes the whole operation very easy. For a list of sequentially-numbered items, you can move an item up by decrementing its position and incrementing the position number of whatever the previous decrement came up with. (In other words, item 5 would become 4 and what was item 4 becomes 5, effectively a swap as Morons described in his answer.) Moving it down would be the opposite. Index your table by whatever uniquely identifies a list and position and you can do it with two UPDATEs inside a transaction that will run very quickly. Unless your users are rearranging their lists at superhuman speeds, this isn't going to cause much of a load.

 

 

Drag-and-drop moves (e.g., move item 6 to sit between items 9 and 10) are a little trickier and have to be done differently depending on whether the new position is above or below the old one. In the example above, you have to open up a hole by incrementing all positions greater than 9, updating item 6's position to be the new 10 and then decrementing the position of everything greater than 6 to fill in the vacated spot. With the same indexing I described before, this will be quick. You can actually make this go a bit faster than I described by minimizing the number of rows the transaction touches, but that's a microoptimization you don't need until you can prove there's a bottleneck.

 

 

아래는 관련된 모든 Row 를 전부 업데이트 하지 않는 방식.

 

GreenHopper way

100, 200, 300, ... 과 같이 일정 간격을 두고 새롭게 생성하며 순서를 변경할 경우 그 사이 중간값으로 업데이트해주면 된다.

 

 

Global Rank/Rank Field

각각의 rank 가 레퍼런스를 가지고 링크드 리스트 형태를 가지도록 한다.

I have a page where the user will place a number of items.

 ________________
| -Item1         |
| -Item2         |
| -Item3         |
| -Item4         |
|________________|

These items have must stay in a the order the user gives them. However this order may be changed an arbitrary number of times by the user.

 ________________
| -Item1         |
| -Item4         |
| -Item2         |
| -Item3         |
|________________|

Approach 1

My original thought was to give the items an index to represent thier place in the list

Page           Item
-----------    ---------------
FK | pid       FK | pid 
   | name      PK | iid 
                  | index
                  | content 

With this solution you can select items where pid = Page.pid and order by index which is convenient. However every time you change the order you have to change anywhere between one other item (best case) and all the other items (worst case).

 

Approach 2

I also considered making a "linked list" like data structure where each item points to the next item in the list.

Page           Item
-----------    ---------------
FK | pid       FK | pid 
   | name      PK | iid 
                  | next
                  | content 

This potentially makes changing the order less expensive but we would have to rely on front end programming to extract the order.

 

 

 

 

LexoRank, Jira 의 현재 ranking 시스템 방식이다.

https://confluence.atlassian.com/jirakb/understand-the-lexorank-managment-page-in-jira-server-779159218.html

 

Bucket, Balancing, Marker Row 라는 부분이 나온다.

기본적으로는 AAA, BBB, CCC, DDD 와 같이 문자열로 rank 를 사용하며 CCA, CCB, CCC, CCD,  가 되었을 경우 Balancing 이라는 절차를 통해 Bucket (0, 1, 2 값의 순환) 값을 0 => 1, 1 => 2, 2 =>0 으로 변경해주면서 다시 AAA, BBB, CCC, DDD 와 같이 셋오프가 있는 값으로 밸런싱해준다. 그래서 실제로는 0|DDA, 0|DDB, 0|DDC, 0|DDD => 1|BBB, 1|CCC, 1|CCD, 1|DDD 와 같은 값의 형태를 가진다. 이렇게 문자열로 rank 값을 구성하고 밸런싱 절차를 추가해주면 무한대로 순서 정보의 변경이 가능한 듯 보인다. Marker Row 라는 부분도 나오는데 rank 값의 min, max 및 관련 메타 데이터와 같은 것을 가지는 부분으로 보인다.

https://www.youtube.com/watch?v=OjQv9xMoFbg