locked
Doubly Linked List Design for Performance RRS feed

  • Question

  • What is the best way to implement doubly linked lists for performance?

    Doubly linked list page: http://richardbowles.tripod.com/cpp/linklist/doublist.htm

    Sample list:

    USE tempdb;
    GO
    SELECT ROW_NUMBER() OVER (ORDER BY name) AS ID, ProductName = name
    INTO dList
    FROM AdventureWorks2008.Production.Product
    
    SELECT * FROM dList ORDER BY ID
    /*
    ....
    348	Mountain-400-W Silver, 42
    349	Mountain-400-W Silver, 46
    350	Mountain-500 Black, 40
    351	Mountain-500 Black, 42
    352	Mountain-500 Black, 44
    353	Mountain-500 Black, 48
    354	Mountain-500 Black, 52
    355	Mountain-500 Silver, 40
    ....
    */
    

    Kalman Toth, SQL Server & Business Intelligence Training; SQL 2008 GRAND SLAM
    Tuesday, July 27, 2010 1:04 AM

Answers

  • Right, but you don't need a linked list to maintain a set with order.  And display order is different than processing order. 

    Usually, dealing with order is doable using set logic in correlated subqueries, unless it is not possible.

    I feel like I am missing something, and I am intrigued :)

     


    Louis

    Thursday, July 29, 2010 3:45 AM

All replies

  • What would the purpose be? And what kind of performance?  Maintaining? Traversing? And would the order be random? Or ordered?

    I mean, ideally, not needing order between items to traverse is one of the primary goals of relational database design.


    Louis

    Wednesday, July 28, 2010 4:11 AM
  • List processing, similar to tree processing (recursive CTE from SQL Server 2005 and on).

    Always ordered like running total for example.  Sample lists with order defined by ID:

    -- ListA
    SELECT ID=ROW_NUMBER() OVER (ORDER BY NEWID()), Name
    FROM AdventureWorks2008.HumanResources.Department
    /* ID	Name
    1	Production
    2	Human Resources
    3	Sales
    4	Document Control
    5	Marketing
    6	Engineering
    7	Information Services
    8	Production Control
    9	Research and Development
    10	Purchasing
    11	Tool Design
    12	Executive
    13	Quality Assurance
    14	Finance
    15	Shipping and Receiving
    16	Facilities and Maintenance
    */
    
    -- ListB
    SELECT ID=ROW_NUMBER() OVER (ORDER BY Name DESC), Name
    FROM AdventureWorks2008.HumanResources.Department
    /* ID	Name
    1	Tool Design
    2	Shipping and Receiving
    3	Sales
    4	Research and Development
    5	Quality Assurance
    6	Purchasing
    7	Production Control
    8	Production
    9	Marketing
    10	Information Services
    11	Human Resources
    12	Finance
    13	Facilities and Maintenance
    14	Executive
    15	Engineering
    16	Document Control
    */
    -- ListC
    SELECT ID=ROW_NUMBER() OVER (ORDER BY LEFT(Name,1), NEWID()), Name
    FROM AdventureWorks2008.HumanResources.Department
    /* ID	Name
    1	Document Control
    2	Executive
    3	Engineering
    4	Facilities and Maintenance
    5	Finance
    6	Human Resources
    7	Information Services
    8	Marketing
    9	Production
    10	Purchasing
    11	Production Control
    12	Quality Assurance
    13	Research and Development
    14	Sales
    15	Shipping and Receiving
    16	Tool Design
    */
    

    Kalman Toth, SQL Server & Business Intelligence Training; SQL 2008 GRAND SLAM
    Wednesday, July 28, 2010 7:01 AM
  • Right, but you don't need a linked list to maintain a set with order.  And display order is different than processing order. 

    Usually, dealing with order is doable using set logic in correlated subqueries, unless it is not possible.

    I feel like I am missing something, and I am intrigued :)

     


    Louis

    Thursday, July 29, 2010 3:45 AM
  • Assume there are millions of lists like in the posts above, what is the best table design for them?

    The [next member pointer] is ID+1, the [previous member pointer] is ID-1.


    Kalman Toth, SQL Server & Business Intelligence Training; BI TRIO 2008
    Saturday, July 31, 2010 6:41 AM